[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리4(아침 산책)

BOJ 21606 아침 산책

난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골3

사용 알고리즘 or 자료 구조 : DFS / BFS

처음 생각한 풀이

단순히 node와 edge가 tree형태로 주어지니까 당연히 실내 전체 순회를 돌며 실내에서 시작해서 다음 노드가 실외라면 dfs를 한번 더 실행하고 실내라면 dfs를 마치고 답을 +1 시켜주는 것으로 생각하고 풀었더니 서브 태스크의 제한조건을 모두 만족하지 못하고 시간초과가 떠버렸다.

 

시간 초과가 뜨는게 당연한 게 2번 같은 경우에는 edge가 상당히 많아 dfs를 굉장히 많이 호출하여 시간 초과가 안나도 메모리 초과가 뜰 것인게 당연하고, 5번의 경우에도 마찬가지일 것이다.

 

그럼 이걸 어떻게 풀어야할까? 생각해봤지만 도무지 떠오를것 같지 않아 구글에서 접근법 만을 찾아봤다.

구글링 이후 풀이

접근법 자체는 굉장히 단순했다.

 

실내를 기준으로 순회를 돌지말고 실외를 기준으로 순회를 돌면 되는 것이었다.

 

무슨 소리냐 하면 실외 노드를 기준으로 순회를 돌며 해당 실외 그룹과 연결된 실내 노드의 개수를 세기만 하면 되는 것이다.

그렇게 되면 우리는 어차피 실내 => (임의의 경로) => 시작과 다른 실내 로 가는 경로의 개수를 세면 되는 것이므로 서로 다른 실내 노드를 순서 상관없이 두 개 고르는 경우의 수만 세주면 되는 것이다.

출처 : https://prodyou.tistory.com/16

이 그림과 같은 경우에는 실외 그룹과 연결된 실내 노드의 개수가 14개 이므로 이 경우 아침 산책 경로의 개수는 14 * 13 = 182가 된다.

 

여기서 조심해야되는 것은 다음 그림들 같은 경우이다.

출처 : https://prodyou.tistory.com/16

실외 그룹이 2개 이상으로 나누어지는 경우.

 

이 경우는 순회를 잘 돌며 각 실외 그룹에서의 산책 경로 개수를 각각 구해서 더해주기만 하면 된다.

출처 : https://prodyou.tistory.com/16

 

이 경우도 가능하므로 정답에 잘 포함시켜보도록 하자.

 

참고로 이 경우는 왼쪽 실내 => 오른쪽 실내, 오른쪽 실내 => 왼쪽 실내 로 두가지 경우의 수가 나온다.

 

이런 방식을 잘 구현하면 아침 산책은 만점을 받고 해결할 수 있다.

(참고로 dfs, bfs 방식 둘 다 구현 가능하니 편한 쪽으로 구현하도록 하자.)

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

sys.setrecursionlimit(10**7)

# dfs 방식 (접근 참고)

# def dfs(start):

#     inside = 0

#     for next in edge[start]:

#         if A[next - 1] == '0':

#             if visited[next] == False:

#                 visited[next] = True

#                 inside += dfs(next)

#         else:

#             inside += 1

#     return inside

# bfs 방식 (원래 내 방식)

def bfs(start):

    inside = 0

    queue = []

    queue.append(start)

    while queue:

        cur = queue[0]

        queue.pop(0)

        for next in edge[cur]:

            if A[next - 1] == '0':

                if visited[next] == False:

                    visited[next] = True

                    queue.append(next)

            else:

                inside += 1

    return inside

N = int(sys.stdin.readline())

A = list(str(sys.stdin.readline().strip()))     # A[i] = 1 이면 실내, 0 이면 실외

edge = [[] for _ in range(N + 1)]

visited = [False for _ in range(N + 1)]

ans = 0

for i in range(N - 1):

    a, b = map(int, sys.stdin.readline().split())

    edge[a].append(b)

    edge[b].append(a)

    if A[a - 1] == '1' and A[b - 1] == '1':     # 실내 to 실내가 가능하므로 두가지 경우의 수 추가

        ans += 2

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

    inside = 0

    if A[i - 1] == '0':     # 실내 공간에서 탐색을 시작하는 것이 아닌, 실외 공간에서 연결된 실내 공간 개수를 조사

        if visited[i] == False:

            visited[i] = True

            # inside = dfs(i)       # dfs 방식(접근 참고)

            inside = bfs(i)         # bfs 방식(내 방식)

    ans += inside * (inside - 1)        # 하나의 실내 공간에 연결되어있는 실내 공간에 대해, 순서 관계없이 실내 공간 2가지를 고르는 경우의 수 추가

print(ans)