[WEEK03/DAY04] 백준 21606번 : 아침 산책

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

21606번: 아침 산책

매일 다른 경로로 아침 산책을 하고 싶어?

하고 싶어? 진짜?

 

 

문제 해석 :

'서울과학고의 N개의 장소를 N-1개의 길이 잇는 트리 형태로 단순화했다'라는 말은,

모든 장소가 이어져 있으며

임의의 장소 U와 V 사이를 직접 잇는 간선은 단 하나만 존재한다는 뜻이다.

 

그리고 문제의 주요 조건을 보면 시작점과 끝점은 반드시 실내여야 하고

경로 중간에 실내가 있어서는 안된다.

이 말인즉슨 경로의 모습은

실내 - 실내

실내 - (실외)  - ...(실외)... - (실외) - 실내

위와 같은 형태가 되어야 한다.

 

입력으로

장소의 개수 N,

실내/실외 구분자 (1: 실내 / 0: 실외),

N-1개의 간선 정보 u, v가 각 줄마다 주어진다.

 

 

접근 :

우선 처음에 한 생각은 이렇다.

1. 모든 장소 중에 실내 장소만을 출발점으로 선정하여 DFS(Depth-First Search)로 경로 탐색

2. 탐색 중 실내를 만나면, 도착점으로 선정하고 경로 카운트 추가.

3. 탐색 중 실외를 만나면, 해당 지점에서 DFS를 재귀호출.

 

이렇게 하면 모든 가능한 경로를 탐색하므로 정답이 나오고

108점을 맞을 수 있다.

200점이 만점이다.

 

왜 또 시간초과야?

당연히 200,000개의 정점에 대해 199,999개의 간선을 하나하나 재귀호출로 탐색하면 오래 걸리겠지...

더군다나 A - B에서 B - A로 거꾸로 가는것도 또 다른 코스가 된다.

그걸 하나하나 따로 세면 당연히 오래 걸리는 게 맞다.

 

(시간초과가 난 108점짜리 코드)

from collections import defaultdict
import sys

# 반복문으로 모든 정점 순회: 실내일때만 출발점으로 선정하여 깊이우선탐색으로 경로 탐색.
# 다음 장소가 실내이면, 그 곳을 도착점으로 할 수 있으므로 경로에 추가하고 다음 탐색을 한다.
# 다음 장소가 실외이면, 추가하지 않고 다음 탐색을 한다.

def DFS(v:int):
    '''정점의 index를 받아서 깊이 우선으로 탐색합니다.'''
    global route_count
    for i in net[v]:
        if i not in visited:
            visited.add(i)
            if A[i-1] == 1: route_count += 1
            else: DFS(i)


N = int(input())
A = list(map(int, list(input()))) # 장소 n에 대하여 A[n-1]이 1이면 실내, 0이면 실외.
net = defaultdict(list)
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    net[u].append(v)
    net[v].append(u)

route_count = 0

for i in range(1, N+1):
    visited = set()
    if A[i-1] == 1:
        visited.add(i)
        DFS(i)

print(route_count)

 

그러니 접근을 달리해서,

실외를 기준으로 잡고 가능한 경로의 수를 찾는 것이 낫다.

 

위와 같은 트리가 있다고 해보자.

실내 노드 수는 3개이고, 실외 하나에 연결되어 있다.

이때 실내에서 출발해서 다른 실내로 도착할 수 있는 경우의 수는 6이다.

N개 중에 하나를 고르고, 나머지 N-1개 중에 하나를 고르는 것이기 때문에

N(N-1)개의 경우의 수가 나오게 된다.

 

이 방법은 더 큰 트리로 확장하여도 유효하게 작용한다.

뭐가 많아졌다.

복잡해 보이지만, 여전히 트리 형태이고

이 트리에서 실내 -> 실내로 갈 수 있는 경로는 N(N-1)개이다.

그림에는 실내 노드가 총 14개 있으므로, 14*13 = 182

즉 182가지의 경로가 존재한다.

 

역시나 나는 수학에 약해서, 왜 이게 가능한건지 증명할 수는 없다.

하지만 귀납적 추론에 의해 N이 충분히 커져도 이 방법이 가능하다고 해보자.

 

그러면 실외 노드 하나를 잡고, DFS로 모든 실외노드를 탐색하며 (BFS로 탐색해도 상관 없다)

각 실외 노드가 가지고 있는 실내 노드들의 개수를 모두 합해주고,

실내 노드 개수들의 총합 N에 대하여 N(N-1)을 하면 가능한 경로가 몇 가지인지 알 수 있다.

 

하지만 아직 간과하고 있는 두가지가 있다.

이런 식으로 중간에 실내가 끼어있게 되면,

우리는 실내가 나왔을 때 탐색을 중단할 것이기 때문에 저 건너편의 노드들은 탐색하지 못하게 된다.

그래서 DFS를 일단 돌리고, 방문한 실외 노드들을 제외한 나머지 노드들에 대해 다시 돌리는 방법으로

실외 노드들을 모두 탐색해 주어야 한다.

 

그리고 마지막 하나 더,

작고 귀엽다.

작고 귀엽지만 위와 같은 경로도 엄연히 2가지의 경로다. (왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽)

그래서 이것도 추가해 주어야 한다.

 

 

최종적으로 구현한 200점 짜리 코드를 첨부한다.

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def DFS(v:int):
    indoor = 0
    for i in net[v]:
        if A[i-1] == 0:
            if i not in visited:
                visited.add(i)
                indoor += DFS(i)
        else: indoor += 1

    return indoor


N = int(input())
A = list(map(int, list(input()))) # 장소 n에 대하여 A[n-1]이 1이면 실내, 0이면 실외.
net = defaultdict(list)
route_count = 0

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    net[u].append(v)
    net[v].append(u)
    if A[u-1] == 1 and A[v-1] == 1:
        route_count += 2 # 실내끼리 인접했을 경우 경로를 2개 더해준다.

visited = set()
for i in range(1, N+1):
    indoor = 0
    if A[i-1] == 0:
        if i not in visited:
            visited.add(i)
            indoor = DFS(i)

    route_count += indoor*(indoor-1)

print(route_count)