반응형
https://level.goorm.io/exam/195701/%EB%8C%80%EC%B2%B4-%EA%B2%BD%EB%A1%9C/quiz/1
해당 문제는 변화하는 그래프에서 최단 거리를 찾는 문제입니다.
문제
풀이
from collections import deque
n, m, s, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
def bfs(s, e, avoid):
visited = [False] * (n + 1)
queue = deque()
queue.append((s, 1))
while queue:
node, distance = queue.popleft()
if node == e:
return distance
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor] and neighbor != avoid:
queue.append((neighbor, distance + 1))
return -1
for i in range(1, n + 1):
if s == i or e == i:
print(-1)
else:
result = bfs(s, e, i)
print(result)
1. 양방향으로 넣어주고 popleft()하면 방문처리, 시작부터 거리와 같이 튜플로 넣어주어 이동할때마다 +1 하는 개념
2. 만약 거리가 각각 다르다면 조건에 거리가 적다면 갱신하는 방향으로 넣어주어야함
반응형
'알고리즘' 카테고리의 다른 글
[BOJ/동적 프로그래밍] 14501 퇴사 (0) | 2023.09.19 |
---|---|
[구름톤 챌린지 종료] Day 20 - 연결 요소 제거하기(그래프 탐색) (0) | 2023.09.12 |
[구름톤 챌린지] Day 18 - 중첩 점(동적 프로그래밍) (0) | 2023.09.12 |
[구름톤 챌린지] Day 17 - 통신망 분석(DFS/BFS) (0) | 2023.09.12 |
[구름톤 챌린지] Day 16 - 연합(그래프 탐색) (0) | 2023.09.12 |