알고리즘

[구름톤 챌린지] Day 19 - 대체 경로(그래프 최단 경로)

motti 2023. 9. 12. 18:11
반응형

https://level.goorm.io/exam/195701/%EB%8C%80%EC%B2%B4-%EA%B2%BD%EB%A1%9C/quiz/1

 

구름LEVEL

난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.

level.goorm.io

해당 문제는 변화하는 그래프에서 최단 거리를 찾는 문제입니다.


문제


풀이

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. 만약 거리가 각각 다르다면 조건에 거리가 적다면 갱신하는 방향으로 넣어주어야함

반응형