SWEA 5102 노드의 거리

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

문제소개

- V개 노드와 E개의 간선이 주어진다.
- 출발 노드(S)에서 도착노드(G)까지 가려면 최소 몇 개의
  간선을 지나야하는지 알아내는 프로그램을 작성
- 예를 들어 다음 그래프에서 1(S)에서 6(G)까지 가는데 
  두 번 이동하므로 2를 출력한다

풀이접근

- 최단거리 구할 땐 bfs로 기준점 기준으로 양방향 탐색

코드

# 앞뒤로 추가와 삭제가 가능한 양방향 큐(deque)
from collections import deque

def bfs(start, end):
    # 시작점 설정 및 방문처리
    Q.append(start)
    visited[start] = 1
    while Q:
        v = Q.popleft()
        for w in G[v]:
            # 방문하지 않았다면 
            if not visited[w]:
                # 방문처리하고 거리 설정
                visited[w] = 1 
                distance[w] = distance[v] + 1
                Q.append(w)
                # 도착하면 거리 반환 
                if w == end:
                    return distance[w]
    return 0

for tc in range(1, int(input()) + 1):
    V, E = map(int, input().split())
    
    # 그래프 표시할 2차원 행렬
    G = [[] for _ in range(V+1)]
    
    # 방향이 없는 그래프이므 양방향 설정
    for i in range(E):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    start, end = map(int, input().split())
    
    # 방문처리, 거리계산을 위한 리스트 생성
    visited = [0] * (V + 1)
    distance = [0] * (V + 1)
    
    Q = deque()
    
    print(f'#{tc} {bfs(start,end)}')

 1
 6 5
 1 4
 1 3
 2 3
 2 5
 4 6
 1 6


#1 2

변수 확인

Q 

deque([])

G # 노드와 간선을 나타낸 2차원 행렬 그래프

[[], [4, 3], [3, 5], [1, 2], [1, 6], [2], [4]]

visited # 방문처리 (인덱스 0 값은 무시)

[0, 1, 1, 1, 1, 1, 1]

distance # 노드별 거리표시 (인덱스 0 값은 무시)

[0, 0, 2, 1, 1, 3, 2]