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

문제

V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다.

주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오.

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다.

   

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

 

 

 

 

내 생각

BFS 문제이다 !

그래프 문제들은 내가 아주아주아주아주 어려워 하는 문제라서 연습의 필요성을 많이 느끼고 있다! 더더 많이 해봐야하지만, 이 문제는 아주 기본적인 문제!

코드에 주석을 한줄한줄 설명을 적었다 !

 

1) 입력받기 : V, E, node, S, G

2)노드 별 연결 노드 저장(양방향) : 방향성이 없기 때문에 양쪽으로 다 저장을 해줘야 한다!

3) BFS 함수

3-1) 방문처리를 저장 할 visited와 거리계산한 것을 저장할 distance가 필요하지만, queue에 노드와 간선 수를 같이 저장하였다.

반복 3-2 ~ 3-4 ) 큐가 비어있지 않은 동안

3-2)  큐의 첫번째 원소 빼서 노드 탐색 (방문처리도 함께 해준다.)

3-3) 방문하지 않고 도착노드이면? → return 간선 수 + 1

3-4) 방문하지 않은 노드이면? → 큐에 넣기 

 

 

 

 

내 코드

from collections import deque

def bfs(S, G):
    # 방문처리
    visited = [False] * (V + 1)
    # 큐에 (노드, 간선 수) 같이 저장
    queue = deque([(S, 0)])
    # 출발점 방문을 처리
    visited[S] = True 
    while queue:  # 큐가 비어있지 않은 동안
        n, cnt = queue.popleft()  # 큐의 첫번째 원소 반환
        if not visited[n]:  # 방문되지 않은 곳이라면
            visited[n] = True  # 방문한 것으로 표시
        for i in node[n]:  # 노드 탐색
            if not visited[i] and i == G:  # 방문되지 않은 곳 and 도착노드면
                return cnt + 1 # 간선의 개수 + 1
            elif not visited[i]: #방문되지 않은 노드이면
                queue.append((i, cnt + 1))  # 큐에 넣기 
    return 0

T = int(input())
for test_case in range(1, T + 1):
    # 1. 입력받기
    V, E = map(int, input().split())
    node = [[] for _ in range(V + 1)]
    # 2. 노드 별 연결 노드 저장(양방향)
    for _ in range(E):
        i, j = map(int, input().split())
        node[i].append(j)
        node[j].append(i)  
    S, G = map(int, input().split())
    print('#{} {}'.format(test_case, bfs(S, G)))