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

📌큐 문제출처   https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg

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

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

 

---

문제풀이  - 큐

💡 PASS

# 5102. [파이썬 S/W 문제해결 기본] 6일차 - 노드의 거리
 
def bfs(v): # 노드1
    q = [] # 노드 번호만 넣는 큐
    q.append(v) # 노드1
    visited[v] = True
    while q: # 큐가 빌 때까지 
        v = q.pop(0) # 앞부터 pop
        for i in range(E): # 방향성 없기 때문, 노드 앞 뒤 다 검사하자
            if node_to_node[i][0] == v and visited[node_to_node[i][1]] == False: #  앞
                val = node_to_node[i][1]
                q.append(val) # 앞 맞으면 뒤노드를 큐 넣기
                distance[val] = distance[v] + 1 # 연결노드 다음이므로 +1
                visited[val] = True
 
            if node_to_node[i][1] == v and visited[node_to_node[i][0]] == False: #  뒤
                val = node_to_node[i][0]
                q.append(val) # 뒤 맞으면 앞노드를 큐 넣기
                distance[val] = distance[v] + 1
                visited[val] = True
 
for testCase in range(1, 1 + int(input())):
    V, E = map(int, input().split())
    node_to_node = [list(map(int, input().split())) for _ in range(E)]
    # print(node_to_node) # [[1, 4], [1, 3], [2, 3], [2, 5], [4, 6]]
    start, end = map(int, input().split()) # 노드1 => 노드6
 
    visited = [False] * (V + 1) # 번호별 방문
    distance = [0] * (V + 1) # 번호별 도달거리
    bfs(start) # 시작점부터 출발 # 노드1부터 시작 
 
    print(f"#{testCase}", distance[end]) # 도착점의 도달거리