[백준] 16953, 2667 (파이썬)

지금까지와 동일하게 그리디 문제와 BFS,DFS 문제를 풀었다. 그리디 문제에서 BFS를 이용하면 더 쉽게 풀 수 있는 문제가 있었기에 그와 관련된 코드도 시도하여 업로드하였다. 확실히 BFS,DFS 문제에 대해서 익숙해지긴 했다. 하지만 손쉽게 푸는 경지가 아니기에 노력이 더 필요하다. 이번 주에 더 시간을 투자해야겠다.

백준 16953번 A → B

# 그리디와 BFS를 이용해도 되는 문제였다.
# BFS 이용코드는 생각해내지 못했다. 노력이 더 필요하다.
'''BFS 이용코드
import sys
from collections import deque
a,b = map(int,sys.stdin.readline().split())
queue = deque([(a,1)])
res = -1
while queue:
    i, cnt = queue.popleft()
    if i == b:
        res = cnt
        break
    if i*2 <= b:
        queue.append((i*2,cnt+1))
    if int(str(i)+'1')<=b:
        queue.append((int(str(i)+'1'),cnt+1))
print(res)
'''
import sys
from collections import deque
a,b = map(int,sys.stdin.readline().split())
cnt = 1
while True:
    if b==a:
        break
    elif (b%2 !=0 and b%10 !=1) or (b<a):
        cnt = -1
        break
    else:
        if b%10 == 1:
            b//=10
            cnt+=1
        else:
            b//=2
            cnt+=1
print(cnt)

백준 2667번 단지번호붙이기

import sys
N = int(sys.stdin.readline())
# 2차원 리스트 정보
graph = []
cnt = []
for _ in range(N):
    graph.append(list(map(int,sys.stdin.readline().strip())))
# 특정노드와 연결된 모든 노드 방문
def dfs(x,y):
    # 범위벗어나면 중지
    if x<0 or x>=N or y<0 or  y>=N:
        return False
    if graph[x][y] == 0:
        return False
    # 현재노드 방문 안한 경우
    global count
    count += 1
    # 방문처리
    graph[x][y] = 0
    # 재귀호출
    dfs(x-1,y)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True
count = 0
res = 0
for i in range(N):
    for j in range(N):
        if dfs(i,j) == True:
            cnt.append(count)
            res += 1
            count = 0
print(res)
cnt.sort()
for i in range(res):
    print(cnt[i])