SWEA 5102 - 노드의 거리

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

 

처음 든 생각

- 이건 무조건 BFS다 -> 큐로 구현하고 방문 여부에 따라 반복문으로 노드를 하나씩 추가해주면서 확인하면 된다

- 이동한 거리를 측정하기 위해서 노드 번호와 거리를 같이 다뤄야겠다.

 

나의 답

T = int(input())
from collections import deque
for test_case in range(1, T + 1):
    V, E = map(int,input().split())
    g = [[] for _ in range(V+1) ]
    for _ in range(E):
        a,b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    S,G = map(int,input().split())
    visited = [0 for _ in range(V+1)]
    q = deque([[S,0]])
    answer = []
    while q:
        t = q.popleft()
        if t[0] == G:
            answer = t
            break
        elif visited[t[0]] == 0:
            visited[t[0]] = 1
            for i in g[t[0]]:
                if visited[i] == 0:
                    q.append([i, t[1] + 1])
    if answer:
        print(f"#{test_case} {answer[1]}")
    else:
        print(f"#{test_case} 0")

 

먼저 각각의 노드가 연결된 그래프를 만들기 위해서 N+1 개의 빈 배열을 선언해준다. 인덱스로 변환하지 않고 노드의 번호를 그대로 사용하기 위해 맨 앞의 빈 배열도 추가했다. 그 다음 연결된 노드를 추가해줌으로써 그래프를 완성한다.

 

방문 여부를 확인하는 리스트와 방문 노드를 관리할 큐를 만들고 [ 노드 번호, 거리 ] 형식으로 큐 안에 데이터를 넣어준다.

 

다음 반복문을 돌면서 전형적인 BFS의 알고리즘을 따라가면 된다. popleft 한 후에 도착점에 도달했다면 정답을 찾은 것이므로 반복문을 나가고 아니라면 그 노드를 방문 처리해주고 연결된 노드를 방문한다.

 

---

 

가장 전형적인 BFS 문제였다. 처음에는 G를 찾았을 때 바로 print를 해주면서 break 하려고 했는데 그렇게 되니 못 찾을 경우의 처리가 바로 떠오르지 않아서 그냥 정답 변수 하나 더 선언해서 처리하였다.

 

BFS

- 큐

- 방문 여부 확인

- 연결된 노드 모두 추가

 

이 3가지 매커니즘에 대해서 한 번 더 복습하고 넘어갈 수 있었던 좋은 문제였다.