[SW Expert Academy] 5102. 노드의 거리

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을 출력한다.

 

 

 

풀이)

from collections import deque
 
def BFS():
    global visited
 
    queue = deque()
    # 출발노드인 s 넣어주기
    queue.append(s)
 
    while queue:
        a = queue.popleft()
        for i in range(v + 1):
            # 간선이 연결되어 있고, 방문하지 않았다면
            if graph[a][i] == 1 and visited[i] == 0:
                visited[i] = visited[a] + 1
                # 도착 노드에 도착했을 시 
                if i == g:
                    return visited[i]
                queue.append(i)
    # 도착 노드에 도착하지 못했을 시
    else:
        return 0
 
T = int(input())
for _ in range(T):
 
    v, e = map(int, input().split())
    graph = [[0] * (v + 1) for i in range(v + 1)]
 
    # 방향성이 없는 graph
    for i in range(e):
        a, b = map(int, input().split())
        graph[a][b], graph[b][a] = 1, 1
 
    s, g = map(int, input().split())
    visited = [0] * (v + 1)
    print(f'#{_ + 1} {BFS()}')

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.