[PY] 21606 : 아침 산책

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

실외 좀 다닐 것이지, 실내만 다니겠다고 애쓰면 비타민D 결핍이다.
어쨌든.. 기본적인 테스트 케이스가 되는걸 보고 눌렀는데 부분 채점 3점이 나와서

개선을 위해 조금 생각을 했다. 핵심은 이렇다.

첫째, 출발하는 노드가 실외일 수 없으니 실내인 경우만 dfs를 실시 할 수 있다.
둘째, 진행 할 노드가 실내라면 그렇구나~ 하고 경로 +1을 하고 넘어 갈 수 있다. 가능한 짧게 산책하려는 주인공 덕분이다.
셋째, 이게 문제다. 실외이면 스택에 넣어서 다음을 보도록 했는데, 실외 - 실외면 조금 귀찮아진다.
사실 기본적인 방문체크도 고려를 안했기 때문에.. 이거까지 넣으니 73점까지 확보를 했다.

무슨 말인지 모르겠다.. 좀만 천천히 하고싶다.

import sys
sys.setrecursionlimit(10**6)
caseCnt = int(sys.stdin.readline())
areaStatus = sys.stdin.readline()
edgeList = [[] for _ in range(caseCnt + 1)]
goAvailable = 0

for i in range(caseCnt - 1):
    
    start, dest = list(map(int, sys.stdin.readline().strip().split()))
    edgeList[start].append(dest)
    edgeList[dest].append(start)

def dfs(startVal):
    global goAvailable
    stack = []
    stack.append(startVal)
    visited = [False] * (caseCnt + 1)
    visited[startVal] = True

    while stack:
        item = stack.pop()
        for nextItem in reversed(edgeList[item]):
            if not visited[nextItem]:
                visited[nextItem] = True
                if areaStatus[nextItem - 1] == '0':
                    stack.append(nextItem)
                else:
                    goAvailable += 1
        


for i in range(1, caseCnt + 1):
    if(areaStatus[i - 1] == '0'):
        continue
    dfs(i)


print(goAvailable)