728x90
처음 든 생각
- 이건 무조건 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가지 매커니즘에 대해서 한 번 더 복습하고 넘어갈 수 있었던 좋은 문제였다.
728x90
'스터디 > 코딩테스트' 카테고리의 다른 글
SWEA 5110 - 수열 합치기 (0) | 2024.01.16 |
---|---|
백준 2580 - 스도쿠 python (1) | 2024.01.15 |
SWEA 5099 - 피자 굽기 (4) | 2024.01.13 |
SWEA 5105 - 미로의 거리 (0) | 2024.01.12 |
SWEA 4881 - 배열 최소 합 (2) | 2024.01.10 |