DFS : 아침 산책(백준 21606번)

▶ 문제 : https://www.acmicpc.net/problem/21606

21606번: 아침 산책

##### 문제 #####
# 아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. 
# 서현이는 산책을 위해 서울과학고의 지리를 분석했고, 
# 그 결과 서울과학고를 N개의 장소를 N-1개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. 
# 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고 갈 수 있습니다.
# 아침 산책은 시작점과 도착점을 정하고 시작점에서 도착점까지 
# 트리 위의 단순 경로(같은 점을 여러 번 지나지 않는 경로)를 따라 걷게 됩니다. 
# 트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다.
# N개 장소 중에 일부 장소는 실내이며, 나머지 장소는 실외입니다. 
# 서현이는 산책을 시작하기 전부터 운동을 하는 것을 원치 않기 때문에, 
# 산책의 시작점과 끝점은 모두 실내여야 합니다. 
# 또한, 산책 도중에 실내 장소를 만나면 산책을 그만두고자 하는 욕구가 생기기 때문에, 
# 산책 경로 위에 시작점과 끝점을 제외하고 실내 장소가 있으면 안 됩니다.
# 서현이는 매일 다른 산책 경로를 걷고자 합니다. 서로 다른 산책 경로가 몇 가지 있는지 구해 봅시다.

# ##### 입력 #####
# 첫 줄에는 정점의 수 N이 주어집니다.
# 둘째 줄에는 1과 0으로 이루어진 길이 N의 문자열 A가 주어집니다. 
# i번째 문자 Ai가 1일 경우 i번 장소는 실내이며, 0인 경우 i번 장소는 실외입니다.
# 셋째 줄부터 N+1번 줄까지는 i+2번 줄에 트리의 각 간선을 나타내는 두 정수 ui, vi가 주어집니다. 
# 이는 i번째 간선이 ui번 정점과 vi번 정점을 연결한다는 의미입니다.

##### 출력 #####
# 가능한 서로 다른 산책 경로의 수를 출력합니다.

 

▶ 접근 방법

방문한 정점이 실내인지 혹은 실외인지에 따라 경로 계산을 다르게 할 필요가 있었다.
우선, 정점 별로 실내, 실외 정보를 등록하고 문제 요구 조건에 따라 실내인 정점에서 탐색을 시작했다.
해당 실내 정점의 인접 정점들이 실내이면 전체 경로에 바로 추가해주고,
아니라면 추가적인 작업을 진행하였다. 이 추가적인 작업이 상대적으로 복잡하였다.

우선 실외 정점의 인접 정점을 모두 살펴보면서, 인접 정점 중 실내 정점이 몇 개인지를 계산한다.
실외 정점 다음에 바로 실내 정점이 나오면 그 경우는 산책 경로가 완성되는 것이기 때문이다.
만약 실외 정점의 인접 정점이 실외 정점이라면 해당 경우에 다시 위와 같은 탐색을 진행한다.
이렇게 실외 정점 주변의 실내 정점의 개수를 구한 후, 해당 개수를 바탕으로 경로의 수를 구할 수 있는 점화식을 작성한다.
해당 점화식이 어떻게 도출되는지 확인하고자 한다면,
실외 정점 1개를 실내 정점 3개가 둘러싸고 있는 경우를 생각해보면 된다.

 

▶ 풀이 코드

import sys
sys.setrecursionlimit(100000)

# 전체 정점의 수
num_of_vertex = int(sys.stdin.readline().rstrip())

# 정점 별 실내(1)/실외(0) 정보, 인덱싱을 위해서 맨 앞에 0 추가한다.
vertex_info = [0] + list(map(int, sys.stdin.readline().rstrip()))

# 정점들을 연결한 그래프
vertex_graph = [[] for _ in range(num_of_vertex + 1)]

# 전체 간선의 수는 전체 정점의 수 -1
for _ in range(num_of_vertex-1):
    vertex_1, vertex_2 = map(int, input().split())
    vertex_graph[vertex_1].append(vertex_2)
    vertex_graph[vertex_2].append(vertex_1)

# 실외인 정점이 들어왔을 때 인접한 정점들을 계산헤야 한다.
def DFS(vertex_0):
    count = 0
    # 실외인 정점의 인접 정점을 하나씩 확인하면서
    for adj_vertex in vertex_graph[vertex_0]:
        # 인접 정점이 실내라면, 경로의 수를 추가해주고
        if vertex_info[adj_vertex] == 1:
            count += 1
        # 실내가 아닌 경우,
        else :
            # 아직 방문하지 않은 정점이었다면
            if adj_vertex not in visited:
                # 해당 정점에 대해서 다시 DFS를 하여 경로의 수를 추가한다.
                visited.add(adj_vertex)
                count += DFS(adj_vertex)
    return count


# 전체 경로의 수
total_count = 0

# 단순 경로임을 고려하여 정점들의 방문 여부를 set으로 표현한다.
visited = set()

# 정점의 수만큼 아래 과정을 반복한다.
for i in range(1, num_of_vertex + 1):
    # 정점이 실내라면
    if vertex_info[i] == 1:
        # 해당 실내 정점과 인접한 정점을 살펴본다.
        for adj_vetex in vertex_graph[i]:
            # 인접한 정점이 실내라면 바로 경로의 수를 추가한다.
            if vertex_info[adj_vetex] == 1:
                total_count += 1
    # 정점이 실외라면
    else:
        # 그리고 해당 실외 정점을 아직 방문하지 않았다면
        if i not in visited:
            # 방문 여부를 추가해주고
            visited.add(i)
            # 해당 실외 정점에 대해서 DFS를 실행한다.
            temp = DFS(i)
            # 실외 정점 기준으로 주변에 실내 정점이 몇 개있는지를 계산해주어야 한다.
            # 이 과정은 아래와 같은 점화식으로 표현할 수 있다.
            total_count += temp * (temp -1)

print(total_count)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.20 - [알고리즘] - DFS :트리의 부모 찾기(백준 11725번)

2021.11.20 - [알고리즘] - 이분 그래프(Bipartite Graph)란?

2021.11.22 - [알고리즘] - DFS : 이분 그래프(백준 : 1707번)