[Baekjoon 21606 / Python / 골드3] 아침 산책

문제

 

DFS 문제이다. 트리가 주어지며, 각 노드는 실외/실내의 특성을 갖는다.

산책 루트는 반드시 실내로 시작해서 실내로 끝나야 한다. 그 사이에 실외가 몇개 있든 상관 없다. 이러한 산책 루트가 최대 몇개인지를 출력하면 되는 문제이다. 방향만 바꾼 것도 포함이다. 1->3 , 3->1 이 루트는 별개의 루트이다.

 

 

처음엔 문제 지문 그대로 코드로 옮겨 풀었었다.

import sys

input = sys.stdin.readline

N = int(input()) # 노드 개수

inout = input().strip()

inout = [''] + [int(x) for x in inout] # 실내여부, 노드번호와 동기화를 위해 맨앞 빈값 추가

graph = [[] for _ in range(N + 1)] # 노드 연결정보, 노드번호와 동기화를 위해 맨앞 빈값 추가

for i in range(N - 1):

    a, b = map(int, input().split()) # 연결된 두 노드

    graph[a].append(b) # 양쪽 노드에 연결정보 추가

    graph[b].append(a)

def dfs(graph, node, visited):

    global result

    if not visited[node] and inout[node] == 1: # 현재 노드가 실내일 경우 길 한개 찾은 것

        visited[node] = True

        result += 1

        return

   

    visited[node] = True

    # 현재 노드가 실외일 경우 방문 안 한 인접 노드들 탐색

    for i in graph[node]:

        if not visited[i]:

            dfs(graph, i, visited)

result = 0

for i in range(1, N + 1):

    if inout[i] == 1: # 시작 노드가 실내일 경우에만 탐색

        visited = [False] * (N + 1) # 방문목록 초기화

        visited[i] = True

        dfs(graph, i, visited)

print(result)

 

처음에 푼 코드다.

- 모든 실내 노드를 시작 지점으로 삼아 DFS를 진행했다.

- 진행 중 다른 실내 노드를 만난다면 즉시 return하고 result를 1개 추가했다.

- 진행 중 다른 실외 노드를 만난다면 DFS를 재귀호출했다.

 

문제 지문을 그대로 코드로 옮겨 적은 코드이다. 다만 이렇게 풀면 정답은 나오는데 "시간 초과"가 뜬다. 정확히는 73점이 나왔다. 5개 케이스 중 3개는 통과, 2개는 시간 초과.

모든 실내 노드에 대해서 연산을 진행하는게 비효율적인 것 같다. 방향만 바꾼 경로도 추가 연산을 해 줘야 하기도 하고...

조금 더 효율적인 방법이 필요했다.

 

import sys

sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

N = int(input()) # 노드 개수

inside = 'x' + input() # 실내 여부

graph = [[] for _ in range(N + 1)] # 연결 정보

result = 0

for _ in range(N - 1):

    a, b = map(int, input().split())

    graph[a].append(b)

    graph[b].append(a)

    # 실내끼리 연결된 노드라면 경로 2개 추가

    if inside[a] == '1' and inside[b] == '1':

        result += 2

visited = [False] * (N + 1)

def dfs(node):

    # 특정 노드의 인접 실내 노드 개수 구하는 함수

    visited[node] = True

    count = 0

    for i in graph[node]: # 인접 노드 탐색

        if inside[i] == '1': # 인접 노드가 실내일 경우

            count += 1

       

        elif not visited[i] and inside[i] == '0': # 인접 노드가 실외일 경우 재귀 호출

            count += dfs(i)

       

    return count

# 모든 실외 노드에 대해서 dfs 진행

for i in range(1, N + 1):

    # 어떤 실외 노드의 인접 실내 노드의 개수를 N이라고 했을 때

    # N * (N - 1) 을 하면 경로의 개수를 구할 수 있다

    # 이것을 모든 실외 노드에 대해서 한번씩 진행하면 된다

    if not visited[i] and inside[i] == '0':

        num = dfs(i)

        result += num * (num - 1)

print(result)

 

두번째로 푼 코드다.

- 모든 실외 노드를 기준으로 DFS를 진행하여, 인접한 실내 노드 개수(num)를 파악한다.

- num * (num - 1) 공식을 이용해 result에 모든 경로의 수를 합산해준다.

- 실내 노드끼리 연결된 경우는 입력받을 때 if문을 통해 예외처리하여 result에 경로 2개를 추가한다.

 

실내 노드가 아닌 실외 노드를 기준으로 탐색했다. 그 이유는 실외 노드를 기준으로 경로의 개수를 찾는 기가막힌 공식이 있기 때문이다.

 

특정 실외 노드와 인접한 실내 노드의 개수를 N이라고 했을 때, 해당 실외 노드를 거치는 모든 경로의 수는 N * (N - 1) 이다. 내가 이 공식을 수학적으로 증명하진 못하겠지만 어쨌든 그렇다. 따라서 트리의 모든 경로의 수를 구하는 방법은, 모든 실외 노드에 대하여 이 공식을 적용하고 그것을 전부 더하면 된다. 

 

다만 여기서 추가적인 예외상황이 발생하는데, 바로 실내 노드끼리만 연결되어 있을 경우이다. 2개의 실내 노드가 연결되어 있다면 이것은 경로 2개로 계산해주면 된다. 입력받을 때 바로 체크해주면 되겠다. 3개 이상의 실내 노드는 연결될 수 없다. 정확히는 연결되어도 그게 경로가 될 수 없다. 어차피 실내 노드를 만나면 진행이 끊기니까 3개까지 못 가는 것이다. 그러므로 연결된 2개의 실내 노드에 대해서만 처리를 해 주면 모든 예외상황을 처리할 수 있다.

 

그리고 sys.setrecursionlimit(10 ** 6) 꼭 해줘야 한다. 최대 재귀호출 한계를 설정해 주는 코드인데 이걸 안 해주면 통과가 안된다.

 

결과