[백준-파이썬] 14942(Platinum5)/dfs : 개미

<문제출처>

https://www.acmicpc.net/problem/14942

14942번: 개미

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

개미가 잠에서 깨어나 굴의 입구인 1번 노드를 향한다. 각 노드에서 이동가능한 거리가 제한 되어있을 때 1번 노드쪽으로 최대한 이동한다면 각각의 노드들은 몇번 노드에서 멈출까?

 

<고민 끄적끄적>

개미 굴들은 그래프 구조로 이어져 있다.
각각의 모든 노드에서 1번노드로 갈 수 있는 최대치를 구한다면 시간초과가 날 것이기 때문에 반대로 1번에서 모든 노드의 방향으로 이동기록을 조회하는 방법으로 접근하였다.

1번노드 부터 방문 출발해서 방문했던 노드들은 앞에서 삽입하였고, 소모되는 에너지 누적값들은 뒤에서 삽입하였다.

이동할 때 소모되는 에너지값들을 누적하여 기록해놓고 가지고 있는 에너지가 누적보다 크다면 1까지 갈 수 있는 것으로판단!
그렇지 않고 에너지가 무족하다면 어디정또 까지 갈 수 있는지를 누적값들의 차이를 통해 구해보았다.

사실 이문제는 희소배열을 이용한 문제라고하는데 희소배열이 먼지 몰랐던 나는 그냥 이렇게 풀었다..

 

 

최종코드

import sys; input = sys.stdin.readline
from collections import deque
import bisect
sys.setrecursionlimit(10**7)

n = int(input())
energy = [None] + [int(input()) for _ in range(n)]
arr = [None] + [[] for _ in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    arr[a].append((b, c))
    arr[b].append((a, c))


def binary(e, c1):
    return bisect.bisect_left(c1, e)


def dfs(x, c1, c2):
    if len(c1) == 0:
        #print("정답 :", x,"=", 1)
        ans[x] = 1
    elif energy[x] >= c1[-1]:
        #print("정답 :", x,"=", 1)
        ans[x] = 1
    else:
        #index = binary(energy[x], c1)
        index = binary(c1[-1] - energy[x], c1)
        #print(x, c1, c2)
        #print("부족 : ", c1[-1] - energy[x])

        if (-index-2) < -len(c2):
            #print("정답 :", x,"=", x)
            ans[x] = x
        else:
            #print("정답 :", x,"=", c2[-index-2])
            ans[x] = c2[-index-2]


    visited[x] = True

    for nx, e in arr[x]:
        if not visited[nx]:
            if len(c1) == 0:
                c1.append(e)
            else:
                c1.append(c1[-1] + e)

            c2.appendleft(x)
            dfs(nx, c1, c2)
            c1.pop()
            c2.popleft()


c1 = deque() # 뒤에서 누적값 삽입
c2 = deque() # 앞에서 방문 노드 삽입
visited = [False]*(n+1)
ans = dict()
dfs(1, c1, c2)
for i in range(1, n+1):
    print(ans[i])

-> 문제를 풀때 if문 처리를 꼼꼼히 해주지 않아서 디버깅 흔적들이...난잡하게 나와있군 후후후

방문처리나 탐색은 탐색 조건들을 정말 꼼꼼하게 if문으로 처리하고 else는 최대한 지양하면 좋을 것 같다 -> (풀 때 헷갈림)