백준 11724번 python 풀이 - 아침 산책
문제 링크
해결책
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
sys.setrecursionlimit(10 ** 5)
ans = 0
def dfs_recur(start):
is_visited[start] = True
inside_count = 0
for i in path[start]:
if is_inside[i - 1] == 1:
inside_count += 1
elif is_inside[i - 1] == 0 and is_visited[i] is False:
inside_count += dfs_recur(i)
return inside_count
N = int(sys.stdin.readline().rstrip())
str_inside = sys.stdin.readline().rstrip()
# 1이면 실내, 0이면 실외
is_inside = []
for i in str_inside:
is_inside.append(int(i))
path = [[] for _ in range(N + 1)]
is_visited = [False for _ in range(N + 1)]
for _ in range(N - 1):
_from, _to = map(int, sys.stdin.readline().rstrip().split())
path[_from].append(_to)
path[_to].append(_from)
if is_inside[_from - 1] == 1 and is_inside[_to - 1] == 1:
ans += 2
if sum(is_inside) <= 1:
print(0)
else:
for i in range(1, N + 1):
if is_inside[i - 1] == 0 and not is_visited[i]:
result = dfs_recur(i)
ans += result * (result - 1)
print(ans)
주석으로 달 설명
문제를 푸는 방식은 여러가지지만… 일단은 DFS로 해결했다. 사실 그렇게 잘 이해하기는 못했다. 참고한링크 반드시 다시 보자.
This post is licensed under CC BY 4.0 by the author.