Post

백준 11724번 python 풀이 - 아침 산책

문제 링크

21606번

해결책

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.