[백준] 21606 - 아침 산책 (Python)

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

 

모든 검은색 노드는 흰색 노드를 통과할 수 있고, 검은색 노드는 통과하지 못할 때,

모든 이동 가능한 검은색 노드 사이 경로의 개수를 세는 문제이다.

 

이 문제는 그래프를 단순화시킨 뒤 순열과 트리의 특성을 이용해 개수를 세면 문제를 풀 수 있다.

 

그림과 같이 노드가 구성되어 있다고 해보자.

우리가 구하려고 하는 것은 두 검은색 노드 사이의 경로가 존재하는지 파악하는 것이다.

이 정보를 파악하는데 중요한 것은, 여러개의 인접한 흰색 노드는 우리가 구하려는 것을 찾는 과정에서 전혀 의미가 없다는 것이다.

그러면 이 그래프를 다음과 같이 단순화할 수 있다.

 

 

흰색 노드의 번호는 더 이상 정답을 구하는데 있어 큰 의미가 없다. (코드로 구현할 때는 번호로 구현하긴 했다.)

그리고 이렇게 축소된 그림에서 인접한 검은색 노드간 사이의 경로 개수는 다음과 같이 나눠서 셀 수 있다.

 

 

첫번째 경우, 10, 4, 5, 1 사이에는 서로 오고 갈 수 있으므로

서로 다른 경로의 개수는 4 x 3 = 12

 

두번째 경우, 4, 7 사이에는 서로 오고갈 수 있으므로

서로 다른 경로의 개수는 2 x 1 = 2

 

세번째 경우, 검은색 노드들 사이에는 인접한 경우에만 이동할 수 있으므로, 검은색 노드들로 구성된 컴포넌트 내부 간선의 개수 x 2 를 하면 된다.

간선에 연결된 두 노드가 각각 자신을 시작점으로 해당 간선을 이용하므로, 간선마다 2번씩 이용되기 때문이다.

따라서 7과 8 두 개 노드로 구성된 경우에는 간선이 노드 개수 - 1 = 1 개 이므로

1 x 2 = 2 가 가능한 경로의 수이다.

 

이를 다 더하면

 

12 + 2 + 2  = 16 이다.

 

---

from collections import deque
import sys
input = sys.stdin.readline

BLACK = '1'
WHITE = '0'

n = int(input())
node_info = [0] + list(input())
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)

visit = [False for _ in range(n+1)]
connected_black = [0 for _ in range(n+1)]
d = deque()
for check_node in range(1, n+1):
    if visit[check_node]:
        continue
    d.append(check_node)
    visit[check_node] = True
    while d:
        now_node = d.popleft()
        now_color = node_info[now_node]

        if now_color == BLACK:
            for next_node in graph[now_node]:
                if node_info[next_node] == BLACK and not visit[next_node]:
                    d.append(next_node)
                    visit[next_node] = True
                    connected_black[check_node] += 1
        else:
            for next_node in graph[now_node]:
                if node_info[next_node] == WHITE and not visit[next_node]:
                    d.append(next_node)
                    visit[next_node] = True
                elif node_info[next_node] == BLACK:
                    connected_black[check_node] += 1

answer = 0
for node in range(1, n+1):
    if node_info[node] == BLACK:
        answer += (connected_black[node]*2)
    else:
        answer += (connected_black[node] * (connected_black[node]-1))
print(answer)

 

정답 코드는 위와 같다.

 

대충 로직을 보면, 1번부터 n번까지 모든 노드를 돌면서, 방문한 노드는 건너 뛰었을 때

현재 노드가 검은색 노드라면, 자신을 포함하는 검은색 노드 컴포넌트의 구성 개수를 세고 방문 체크를 한다.

현재 노드가 하얀색 노드라면, 하얀색 노드를 타고 넘어가면서 인접한 검은색 노드의 개수를 센다.

이때 방문체크는 하얀색 노드만하면 되고, 중요한 점은 처음 방문하게 된 하얀색 노드를 기준으로 인접한 검은색 노드의 개수를 세어야 한다.

지금 방문한 노드를 기준으로 셌더니 틀려서 맞왜틀했었다ㅋㅋ

 

최종 결과는 인접한 검은노드를 센 결과를 토대로 순열과 트리 특성으로 위에서 말한대로 게산하면 된다.