1240번 - 노드 사이의 거리

트리가 주어지고 노드 사이의 거릿값이 주어질 때 노드 두 개가 주어졌을 때 해당 노드 사이의 거리를 구하면 되는 문제입니다.

이런 씩으로 말입니다.

---

처음 접근한 방식

문제를 보고 2차원 배열의 DFS로 풀되 그래프의 값에 거리값을 넣어 풀이하면 되겠구나! 하여

for _ in range(N-1):
    a,b,distance = map(int,input().split())
    graph[a][b] = graph[b][a] = distance

이차원 배열을 하나 만들어 a와 b가 이어져 있다는 걸 표현하고 해당 인덱스 value에 거리값을 넣고

    for i in range(len(graph[0])):
        if not visited[i] and graph[N][i] != 0:
            length += graph[N][i]
            length_record.append(graph[N][i])
            dfs(i,end)
    if length_record:
        length -= length_record.pop()

DFS 탐색을 진행하여 depth, 즉 깊이가 증가할 떄마다 graph[N][i]의 value(거릿값)를 합연산하여

    if N == end:
        ans.append(length)

최종적으로 끝값을 만나면 ans에 추가되도록 코딩하니...!

제가 잊고 있었습니다... DFS에서 이차원 배열을 자유롭게 사용하게 되면 배열의 크기가 커져 결과도 자유롭게 나와버린다는 것을...

---

해결방안

위는 문제의 제한 사항입니다.
N의 범위를 1000, M의 범위를 1000으로 지정하고 있습니다.
여기서 생각한 것은 DFS 그래프는 1차원적 배열로 용량을 줄이되 1000 x 1000 해봐야 백만밖에 안되니까 거릿값을 나타내는 그래프는 그대로 2차원 표기로 사용해도 되겠다! 싶었습니다.

---

풀이

N,M = map(int,input().split())
visited = [0]*(N+1)
graph = [[]for _ in range(N+1)]
distance_graph = [[0]*(N+1) for _ in range(N+1)]
length = 0
ans = []
distance_tmp = []

DFS를 사용하기 위한 변수들과 방문여부, 그리고 위에 언급했듯이 거릿값만을 나타내는 distance_graph와 나머지 변수등을 선언해주겠습니다.

for _ in range(N-1):
    a,b,distance = map(int,input().split())
    distance_graph[a][b] = distance_graph[b][a] = distance
    graph[a].append(b)
    graph[b].append(a)

거릿값을 나타내는 그래프는 전에 처음 풀이한 방식과 동일하게 작성해줍니다.
다만 이제 연결된 노드를 나타내는 그래프는 처음 풀이한 방식과 다르게 위와 같이 작성하여

원래였다면 위와 같이 나올 그래프를

1차원적 리스트로 함축시켜 메모리 제한을 피하도록 하겠습니다.

ans_tmp = []
for _ in range(M):
    a,b = map(int,input().split())
    ans_tmp.append([a,b])

다음으로 거릿값을 구해줄 노드를 입력받습니다.

for values in ans_tmp:
    dfs(values[0],values[1])
    distance_tmp = []
    visited = [0]*(N+1)
    length = 0

이제 DFS 함수를 준비하겠습니다. values[0]은 탐색의 시작점, values[1]은 보관만 하고 있다가 만약 변수값이 values[1]과 같아진다면 ans에 최종값 추가하고 return 하는 씩으로 작성할 재귀 종료에 필요한 변수입니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

마찬가지로 메모리 종료에 필요한 함수들 작성하고 DFS 부분 마저 작성하겠습니다.

---

DFS

def dfs(N,end):
    global length
    visited[N] = 1

들어오면 방문표시 해주고

    if N == end:
        ans.append(length)
        return

위에 말씀드렸듯이 탐색중인 구간이 end와 같다면 ans에 답 추가하고 return으로 함수종료 하겠습니다.

    for values in graph[N]:
        if not visited[values]:

현재 탐색중인 구간과 연결된 노드에서 아직 방문하지 않은 노드가 있다면

            distance_tmp.append(distance_graph[N][values])
            length += distance_tmp[-1]

현재 노드와 연결된 노드 사이의 거리를 distance_tmp에 추가하고 length(현재 길이)에는 distance_tmp[-1]을 합연산해줍니다.

            dfs(values,end)

그리고 재귀 넣고

    if distance_tmp:
        length -= distance_tmp.pop()

깊이가 최대로 도달해서 더 이상 탐색할 노드가 없으면 현재 노드와 이전 노드 사이의 거리 (distance_tmp.pop)만큼 빼주면서 하위노드 탐색을 나와줍시다.

for values in ans:
    print(values)

마지막으로 출력하면 됩니다.

---

여담이지만 사실 이런 문제는 BFS를 사용하는게 메모리 또는 시간초과 걱정 없이 풀기 좋을 것 같습니다. 그래도 이런 문제를 강제로 DFS로 풀어 사용력을 향상시키는 데는 괜찮은 것 같습니다.

---