240123_아침 산책

조건

1. 실내에서 산책을 시작해 실내에서 종료한다.
2. 실외에서 산책을 시작하거나 종료할 수 없다.

아이디어

1. DFS방식을 사용한다.
2. 출발 노드에서 다음 노드로 갈때, 다음 노드의 데이터가 1이면 산책을 종료한다.
3. visited를 set을 사용하여 출발 노드와 다음 노드를 넣어줘 돌아가는 것을 방지한다.
4. 1~마지막 노드까지 for문을 돌려 모두 돌린다.

import sys
input = sys.stdin.readline

N = int(input())
list = list(map(int, ' '.join(input().split())))
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
   a, b = map(int, input().split())
   graph[a].append(b)
   graph[b].append(a)

visited = set()
count = 0
def JoggingPath(start, visit):
   global count
   visit.add(start)
   
   for i in graph[start]:
       if i not in visit:
           visit.add(i)
           if list[i-1] == 1:
               count += 1
               continue
           JoggingPath(i, visit)
   
for i in range(1, N+1):
   if list[i-1] == 0:
       continue
   visited = set()
   JoggingPath(i, visited)
   
print(count)

• 처음 visit를 생성시 set함수를 사용하지 않고 [False]를 만들고 사용하였더니 73점이 나왔다. set함수 사용하고 108점 획득하였다.
• 200점 코드는 그래프를 다각형으로 만든 후 n(n-1)를 반환하는 코드라는데 봐도 이해가 되지 않아 내일 옆에 팀원한테 물어봐야할 것 같다.