[SW Expert Academy] 5102번 노드의 거리 python

문제의 저작권은 SW Expert Academy에 있습니다.

5102. [파이썬 S/W 문제해결 기본] 6일차 - 노드의 거리

문제

V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다. 주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오. 예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다.

풀이

그래프 찾기라고 대놓고 말하고 있다. BFS하자.
노드의 개수는 50개니까 인접행렬 해도 되겠다.
서로 연결되지 않는다면, 0을 출력한다.

BFS(G,V)  # g는 그래프, 탐색 시작점 v
    큐생성
    시작점 v를 큐에 삽입
    점 v를 방문한 것으로 표시

우선은 큐에 출발 점을 넣는다.

이때 중요한 것은 visited 체크를 +1 해주면서 bfs 검색을 한다.

도착지 검색은 인큐(append) 이 후에 해도 되지만, 가능하면 큐에서 뺄 때(popleft) 검사를 하면 좋다.

def bfs(s):
    deq=collections.deque()
    visited = [0]*(V+1)
    deq.append(s)
    visited[s] = 1
    while deq:
        p = deq.popleft()
        if p == end:
            return visited[p]
        for i in range(V+1):
            if data[p][i] == 1 and visited[i] == 0:
                deq.append(i)
                visited[i] = visited[p] + 1
    return 1


import collections
import sys
sys.stdin=open("5102노드의거리.txt")
TC = int(input())
for tc in range(1, TC+1):
    V, E = map(int, input().split())

    data = [[0]*(V+1) for _ in range(V+1)]

    for _ in range(E):
        n, m = map(int, input().split())
        data[n][m] = 1
        data[m][n] = 1
    start, end = map(int, input().split())
    c = 1
    c= bfs(start)
    print("#%d %d"%(tc, c-1))