[SWEA] 5102_노드의 거리

📕 문제

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

   

 
노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5<=V=50, 4<=E<=1000
테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 간선의 양쪽 노드 번호가 주어진다.
E개의 줄 이후에는 출발 노드 S와 도착 노드 G가 주어진다.

 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
두 노드 S와 G가 서로 연결되어 있지 않다면, 0을 출력한다.

 

💡 풀이법

1. 방문처리와 지나친 간선의 개수를 저장하는 visited 리스트를 만든다.

2. q라는 queue 리스트를 만든다. (갈 노드들을 저장하는 queue)

3. S에서 처음 시작하고 visited의 S인덱스 위치의 수를 1로 바꾼다.

4. S와 인접한 노드들 중 거치지 않은 곳이 있다면 S까지의 간선의 개수에 1을 더해서 해당 인덱스에 넣는다.

5. 그리고 q에 노드들을 더해준다.

6. 만약 인접한 노드가 도착점 G라면 visited 리스트에서 해당 노드 인덱스의 값을 구해준다.

(대신, 처음을 1로 시작했었기 때문에 1을 빼줌)

 

def bfs(S, G):
    q = [S]
    visited[S] = 1
    while q:
        v = q.pop(0)
        for i in g[v]:
            if visited[i] == 0:
                visited[i] = visited[v] + 1
                q.append(i)

            if i == G:
                return visited[i] - 1
    return 0

T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())
    g = [[] for _ in range(V+1)]
    visited = [0] * (V + 1)

    for _ in range(E):
        i, j = map(int, input().split())
        g[i].append(j)
        g[j].append(i)

    S, G = map(int, input().split())
    answer = bfs(S, G)
    print('#{} {}'.format(tc, answer))