[Python] SWEA 5102 노드의 거리

SW Expert Academy SWEA 5102 노드의 거리는 V개의 노드와 방향성 없는 E개의 간선이 있을 때 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 문제다. 큐 queue, 데크 deque, BFS 알고리즘에 관한 문제로 난이도는 D2다.

 

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

 

SW Expert Academy 5102 노드의 거리 문제 정보

자료구조 / 알고리즘 분류

- queue 큐, deque 데크 / BFS 알고리즘 (Breadth First Search)

난이도

- D2

 

5102 노드의 거리 문제 요약

• 개의 노드 개수와 방향성이 없는 E개의 간선을 가진 그래프가 있다.  (5≤V≤50, 4≤E≤1000)
• 노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.
• 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내어 출력한다.
• 출발 노드와 도착 노드가 연결되어 있지 않으면 0을 출력한다.

 

문제 풀이 과정

1. deque 자료구조를 사용하기 위해 import 한다.
2. 노드 별로 연결된 노드를 저장한 리스트, 방문 여부 리스트를 생성한다.
3. (현재 노드, 지난 간선 개수) 튜플 객체를 원소로 갖는 deque를 생성한다.
4. 큐가 비기 전까지 5~8번 과정을 반복한다.
5. 큐의 첫 번째 원소를 꺼내어 미방문 시 방문하고
6. 방문한 노드와 연결된 노드들을 탐색하여
7. 방문되지 않은 노드면 큐에 삽입하고
8. 방문되지 않은 노드이면서 도착 노드이면 지나간 간선 개수 +1을 리턴한다.
9. 큐가 비면 출발, 도착 노드가 연결되어있지 않은 것이므로 0을 리턴한다.
10. 테스트 케이스 번호, 최소로 지나간 간선 개수를 출력한다.

 

코드 및 설명

• node [] - 노드 별 연결된 노드들을 저장하는 리스트
• visited [] - 노드 별 방문 여부를 저장하는 리스트
• queue - 방문 예정인 노드의 정보 (현재 노드, 지난 간선 개수) 튜플 객체를 원소로 갖는 deque

from collections import deque

def bfs(start, goal):
    # 노드와 지난 간선 개수를 함께 저장
    queue = deque([(start, 0)])
    # 큐가 비어있지 않는 동안
    while queue:
        # 큐의 첫번째 원소 반환
        n, cnt = queue.popleft()

        # 미방문 시 방문으로 표시
        if not visited[n]:
            visited[n] = 1

        # 방문한 노드와 연결된 노드들 탐색
        for j in node[n]:
            # 방문되지 않은 노드이고 도착 노드라면 지나간 간선 개수 +1 리턴
            if not visited[j] and j == goal:
                return cnt + 1
            # 방문되지 않은 노드이면 큐에 삽입
            elif not visited[j]:
                queue.append((j, cnt + 1))

    # 출발, 도착 노드가 연결되어 있지 않으면 0 리턴
    return 0

for tc in range(int(input())):
    node_num, Edge_num = map(int, input().split())
    node = [[] for _ in range(node_num + 1)]
    visited = [0] * (node_num + 1)

    # 노드 별 연결 노드 저장
    for i in range(Edge_num):
        node1, node2 = map(int, input().split())
        node[node1].append(node2)
        node[node2].append(node1)

    start_node, goal_node = map(int, input().split())

    print("#%d %d" % (tc + 1, bfs(start_node, goal_node)))

---

지나간 간선 개수를 어떻게 세야 하나 고민했는데, deque에 현재 노드와 지나간 간선 개수를 함께 저장하면 된다.

 

SW Expert Academy SWEA 5102 노드의 거리 문제는 큐 queue, 데크 deque 자료구조, BFS 알고리즘 활용 문제이며 파이썬으로 구현하였다. 난이도는 D2이다.