[복기] 21060번: 아침 산책

본 글은 아침 산책 풀이를 참고하여 작성하였습니다.

문제

백준 21606번: 아침 산책

알고리즘 분류

• 수학
• 조합론
• 그래프 이론
• 그래프 탐색
• DFS

나의 풀이(108점): DFS

순수 DFS만을 사용했다. DFS 재귀를 사용해서 제한조건 4까지는 뚫었는데 5번은 아무리해도 시간초과가 떠서 108점을 받았다. 로직은 간단하다. 특정 실내에서 DFS를 돌면서 다른 실내에 도착하면 answer += 1을 하며 산책 경로를 찾는다. 재귀 방식을 스택 방식으로 바꾸어도 시간 초과는 마찬가지라 결국 솔루션을 보고 해결했다.

솔루션을 보니 DFS 문제라기보단 수학 문제에 가까운 것 같다. 조합론을 사용해서 DFS의 경우의 수를 줄이는 방법은 상상도 못 해봤다. 또 새로운 것을 배웠다.

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
isInside = input()

edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

answer = 0
visited = [False] * n
def dfs(start):
    global answer
    
    for next in edges[start]:
        if not visited[next]:
            if isInside[next] == '1':
                answer += 1
            else:
                visited[next] = True
                dfs(next)
                visited[next] = False


for start in range(n):
    if isInside[start] == '0' or not edges[start]:
        continue
    
    visited[start] = True
    dfs(start)
    visited[start] = False

print(answer)

솔루션: 조합론 + DFS

아침 산책 풀이

왜 카테고리에 조합론이 있는지 알 수 있었다. 실외를 기준으로 둘러싸고 있는 실내의 개수 n에 대해 "n * (n-1) == 실외를 거쳐가는 경로의 수"이다. 이러면 실외에서 DFS를 돌면서 둘러싸고 있는 실내의 개수만 세면 된다.

예외의 경우로, (a, b) 입력받을 때 둘 다 실내이면, 실내에서 출발해 실내에서 끝나는 경우 2가지(a -> b와 b -> a)를 추가해야 한다. 따라서 이때 +2를 더해준다.

전체 코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(cur, cnt):
    visited[cur] = True
    
    for next in edges[cur]:
        if isInside[next] == '1':
            cnt += 1
        elif not visited[next]:
            cnt = dfs(next, cnt)
    
    return cnt

n = int(input())
isInside = input()

visited = [False] * n
answer = 0
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    if isInside[a-1] == '1' and isInside[b-1] == '1':
        answer += 2

for cur in range(n):
    if isInside[cur] == '1' or visited[cur]:
        continue
    
    temp = dfs(cur, 0)
    answer += temp * (temp-1)

print(answer)