15971번. 두 로봇

http://boj.kr/15971 

 

 

최단거리를 찾는 문제이다. 하지만 BFS가 아닌 DFS로 찾아야 한다. 그 이유는 경로는 단 하나이기 때문이다. BFS로 하면 시간초과가 난다.

경로를 DFS로 풀면서 헷갈린 점이 있는데, 이리저리 경로를 헤매는 BFS 같은 경우가 아니므로 visited를 다시 체크해제할 필요가 없다는 것이다.

한번 방문한 점은 다시 방문하지 않을 것이다. 왜냐면 어떤 한 점으로 가는 방법은 하나이기 때문이다. 다른 루트를 통해 그 점으로 갈 수 없다는 뜻이다.

 

그리고 경로는 단 하나이므로, 출발지에서 목적지까지 가는 경로를 구한 후, 하나의 weight를 뺄 수 있으므로 가장 큰 weight을 빼주면 된다. 두 로봇들이 가장 긴 통로를 사이에 두고 ㅇㅡㅇ 통신을 한다고 보면 된다. 그리고 그 ㅡ를 가장 긴 통로로 선택하면 되고.

 

방법은 이렇지만 파이썬으로 풀기 까다로운 문제인데, 시간초과와 메모리초과가 나기 때문이다.

경로를 N * N의 배열에 저장하면 dfs로 경로 선택을 할 때 매번 N번만큼 반복하게 되므로 시간초과가 난다.

그리고 dfs를 할 때 재귀가 아닌 스택으로 풀면 시간 초과가 난다. (N <= 5000 일때만 통과)

또 재귀를 할 때도 반드시 sys.setrecursionlimit(500000000) 를 넣어줘야 한다.

 

마지막으로 문제에서 점은 1부터 시작한다고 했으므로 점을 입력받은 후 배열 인덱스로 쓰기 전에 -1을 하던가, 배열을 하나 더 크게 만들던가 해야된다는 점을 잊지 말자.

import sys


def dfs(now, max_weight, total):
    if now == end-1:
        print(total - max_weight)
        exit(0)
    for next, d in dist[now]:
        if not visited[next]:
            visited[next] = 1
            dfs(next, max(max_weight, d), total+d)


def dfs_stack():
    stack = [[start-1, 0, 0]]
    while stack:
        now, max_weight, total = stack.pop()
        if now == end - 1:
            print(total - max_weight)
            break
        for next, d in dist[now]:
            if not visited[next]:
                visited[next] = 1
                stack.append([next, max(max_weight, d), total+d])

sys.setrecursionlimit(500000000)

input = sys.stdin.readline
N, start, end = map(int, input().split())
dist = [[] for _ in range(N)]
visited = [0] * N

for _ in range(N-1):
    i, j, d = map(int, input().split())  # 왼쪽방, 오른쪽방, 거리
    dist[i-1].append([j-1, d])  # dist[왼쪽점] = [오른쪽점, 거리]
    dist[j-1].append([i-1, d])  
    # dist[왼쪽점][오른쪽점] = 거리 <- 거리를 dist[N][N]으로 만들면 
    # dfs에서 다음 점을 선택할 때 for문이 무조건 N번 돌아야해서 시간초과
    # dist[왼쪽점][오른쪽점] = 0 인 곳은 빼고 탐색할 수 있도록 해야 한다.

visited[start-1] = 1
dfs(start-1, 0, 0)
#dfs_stack()