Jinho Tech

기본적인 BFS 문제이다. 

from collections import deque

def bfs(node):
    q = deque()
    q.append(node)
    check[node] = 1
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                q.append(n)

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
bfs(1)
m = max(check)
print(check.index(m), m-1, check.count(m))

BFS 문제이다. 인접 행렬, 인접 리스트가 구조가 아닌, 1차원 리스트 구조로 BFS를 구현해주면 된다. 

from collections import deque

def bfs(N, K):
    queue = deque([N])
    while queue:
        node = queue.popleft()
        if node == K:
            return ;
        for n in [node-1, node+1, node*2]:
            if (0 <= n <= 100000) and graph[n] == 0:
                queue.append(n)
                graph[n] = graph[node] + 1
            
N, K = map(int, input().split())
graph = [0]*100001
bfs(N, K)
print(graph[K])