구름톤 챌린지 4주 차 학습 일기(Day 02)

문제

플레이어는 1번부터 N번까지의 번호가 붙은 N개의 도시와 M개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.

플레이어는 차를 타고 S번 도시에서 E번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은 출발 도시와 도착 도시를 포함해 네 개의 도시를 거치는 경로이므로, 플레이어는 해당 경로로는 이동하지 않을 것이다.

 

 

항상 가장 작은 수의 도시를 거치는 경로가 유일하지 않을 수 있다. 아래 그림과 같이 도시와 도로가 주어지고, 3번 도시에서 1번 도시로 이동하고자 할 때 가장 작은 수의 도시를 거치는 경로는 3 → 2 → 1과 3 → 4 → 1의 두 개가 있다. 이런 경우에 플레이어는 두 경로 중 아무 경로나 택해서 이동한다.

 

 

플레이어가 사는 나라에서는 자주 공사를 한다. 일 뒤에는 번 도시에서 하루 동안 공사를 할 예정이다. 어떤 도시에서 공사를 하고 있으면, 그 도시에 연결된 모든 도로를 일시적으로 사용할 수 없다.

어떤 도시에서 공사를 하느냐에 따라 플레이어가 이동해야 하는 경로가 달라질 수 있다. 앞으로 N일 동안 매일 플레이어는 S번 도시에서

E번 도시로 이동한다고 할 때, 각 날마다 플레이어가 이동하는 경로에 포함되는 도시의 수를 구해서 출력해 보자. 단, 출발 도시와 도착 도시에서 공사를 하거나, 두 도시 사이를 이동할 수 없는 경우에는 -1을 대신 출력한다.

 

 

 

 

코드

from sys import stdin as s
from collections import deque

def bfs(city, start, end, visited):
    global leng
    if city == start:
        return
        
    q = deque([[start]])
    
    while q:
        path = q.popleft()
        node = path[-1]
        
        if node == end:
            length = len(path)
            leng = min(leng, length)
        else:
            for to in arr[node]:
                if to == city or to in path or visited[to]:
                    continue
                new_path = list(path)
                new_path.append(to)
                q.append(new_path)
                visited[to] = True

    if leng == 10000:
        ans[city].append(-1)
    else:
        ans[city].append(leng)

if __name__ == '__main__':
    N, M, S, E = map(int, s.readline().split())
    arr = [[] for _ in range(N + 1)]
    ans = [[] for _ in range(N + 1)]

    for _ in range(1, M + 1):
        a, b = map(int, s.readline().split())
        arr[a].append(b)
        arr[b].append(a)

    for i in range(1, N + 1):
        if i==S or i==E:
                continue
        visited = [False] * (N + 1)  
        leng = 10000
        bfs(i, S, E, visited)
    
    for i in range(1, N + 1):
        if ans[i]:
            print(ans[i][0])
        else:
            print(-1)

 

 

느낀점

처음 이문제를 봤을 때 최단 경로를 구하는 문제여서 다익스트라인가?라는 생각이 들었다. 하지만 가중치나 비용 같은 걸 따지지 않고 단지 경로의 길이를 가지고 계산을 하는 문제이다 보니까 bfs로 풀어도 되겠다는 생각을 해서 bfs로 풀었습니다.

우선 문제의 핵심요소는 S번 도시부터 시작해서 E번 도시까지 방문했을 때 모든 경우의 수를 구하고 가장 경로가 짧은 것을 출력하는 것입니다. 제가 문제를 풀 때 막혔던 부분은 경로가 나눠질 때 어떻게 그걸 따로따로 가지고 있을까 라는 생각을 하는 것이 어려웠던 것 같습니다.

new_path로 경로가 나눠질 때 그 케이스 별로 경우의 수를 구해준 다음에 길이를 비교하는 과정은 생각보다 쉬웠고 제출했을 때 시간초과와 런타임 에러가 발생했는데 이걸 해결하기 위해 처음에는 leng의 초기값을 inf로 잡아두고 방문표시를 체크 안 하고 모든 노드를 계속 탐색하니까 에러가 발생했다고 생각했습니다. 방문처리와 leng초기값을 적당한 10000으로 잡아두고 풀이하니 모든 케이스가 통과됐습니다.