[bfs/백준] 2644번 : 촌수계산

- 문제 : https://www.acmicpc.net/problem/2644

 

문제 이해

그래프를 만든 뒤 두 노드 사이에 몇 개의 간선이 있는지 확인하는 문제라고 이해했다. 

간선 개수를 확인하기 위해 bfs를 이용해야 한다. 

(부모 -> 자식) 관계도 있지만 (자식 -> 부모) 관계도 있기 때문에 양방향 간선으로 graph에 저장해야한다. 

 

풀이 로직

- 찾아야하는 두 노드를 first, second라고 한 뒤 양방향 간선 정보를 graph에 저장한다.

- 탐색하는 노드가 찾고자 하는 second 노드라면 answer를 level로 업데이트 해준 뒤 break 한다.

- first노드 부터 그래프 탐색을 시작하는데, visit[first] = 1 을 해준다.

- queue는 [노드, first로부터의 간선 개수]로 설정했다. 

- 연결되었지만 방문하지 않은 노드를 중심으로 탐색한다. 탐색하면서 간선을 하나씩 지나가므로 level + 1 해준다. 

- if 문에서 break 해서 나온 answer라면 -1이 아닌 양수를 출력하고, 그렇지 않다면 -1을 출력한다. 

 

 

정답 풀이 

n = int(input())
first, second = map(int, input().split()) 
m = int(input())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 여기 추가 안 해서 틀림

queue = [[first, 0]]
visit = [0] * (n + 1)
visit[first] = 1
answer = -1
while queue:
    person, level = queue.pop(0)
    
    if person == second:
        answer = level
        break
    
    for each in graph[person]:
        if not visit[each]:
            visit[each] = 1
            queue.append([each, level + 1])

print(answer)