[모각코] 210724 Today I Learned

<백준 18126번 - 너구리 구구>

 

이거 지난 주 토요일 모각코 때 시도했던 문제인데 다른 거 하느라 계속 미뤄서 드디어 오늘 다시 시도했다.

모각코 당일인 17일에는 아예 알고리즘을 잘못 생각하고 있었고, 다음날인 18일에 다시 풀어서 모각코 글을 작성했다.

18일에 푼 코드는 예제만 맞고 제출 돌리면 틀렸었다.

2021.07.17 - [HUFS/HUFS 모각코 캠프] - [모각코] 210717 Today I Learned

 

 

#기존(에 틀린) 코드

import sys

def dfs(v):
    visited[v] = 1
    for i in range(len(adjList[v])):
        w = adjList[v][i][0]
        if not visited[w]:
            dist[w] = max(max(dist), adjList[v][i][1] + dist[v])
            dfs(w)

n = int(sys.stdin.readline())
visited = [0 for i in range(n+1)]
adjList = [[] for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(1, n):
    a, b, c = map(int, sys.stdin.readline().split())
    adjList[a].append([b, c])
    adjList[b].append([a, c])

dfs(1)
print(max(dist))

 

 

난 진짜... 진짜 바보다.

진짜.. 진짜 바보야.

왜 틀린 건지 절대 이해를 못 하겠어서 친구한테 도움을 청했는데 바로 이상한 점을 캐치해주었다.

 

dfs 함수 내부에서 if문이 문제였다.

if not visited[w]:
            dist[w] = max(max(dist), adjList[v][i][1] + dist[v])
            dfs(w)

max(dist) : 지금까지 거리의 최댓값

adjList[v][i][1] + dist[v] : 현재 있는 방까지 걸리는 거리 + 그 전의 방까지 걸리는 거리

 

여기서 중요한 점은 dist[w]를 max(dist), adjList[v][i][1] + dist[v] 의 최댓값을 구해서 저장을 해주면 안 된다는 것이다.

dist[w] = max(max(dist), adjList[v][i][1] + dist[v]) 이렇게 저장을 하면 현재 최댓값보다 최댓값이 나오기 전까지의 값들이 전부 현재 최댓값으로 저장이 된다.

표로 설명을 하자면,

이렇게 되는 것이다.. 와 글로 안 쓰고 이렇게 설명하니까 너무 좋다.

쨌든 그래서 이것만 고쳐주었더니 맞았다..

이걸 못해서... 계속 머리 싸매고 있었다니.... 짜증나고 넘 바보같지만 그래도 풀었으니까 행복하다..

 

 

#맞은 코드

import sys
sys.setrecursionlimit(10**6) #재귀 깊이가 문제인가 싶어서 이 코드도 추가했다.

def dfs(v):
    visited[v] = 1
    for i in range(len(adjList[v])):
        w = adjList[v][i][0]
        if not visited[w]:
            dist[w] = adjList[v][i][1] + dist[v]
            dfs(w)

n = int(sys.stdin.readline())
visited = [0 for i in range(n+1)]
adjList = [[] for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(1, n):
    a, b, c = map(int, sys.stdin.readline().split())
    adjList[a].append([b, c])
    adjList[b].append([a, c])

dfs(1)
print(max(dist))