Cp 8-02 | Notion

11724. 연결 요소의 개수

이 문제는 앞 단계에서 [순열 사이클], [섬의 개수] 문제와 마찬가지로 연결되어져 있는 그래프가 몇 개인지 구하는 문제이다.

문제에서 언급하고 있는 연결 요소(Connected Component)는 연결되어져 있는 하나의 그래프를 의미한다.
DFS 탐색은 임의의 지점에서 탐색을 시작해서 연결된 모든 정점을 탐색한 후에 시작지점으로 되돌아 오고,

BFS 탐색은 임의의 지점에서 탐색을 시작해서 연결된 모든 정점을 탐색한 후에 마지막 지점에서 종료한다.

DFS 이건 BFS 이건 임의의 지점에서 연결된 모든 정점을 탐색하면 일단 탐색이 종료되기 때문에 탐색 종료는 하나의 연결된 그래프가 존재한다고 볼 수 있다.

그래서, 연결 요소의 개수는 탐색이 종료될 때마다 +1씩 증가된다고 볼 수 있다.

트리 구조에서는 루트가 정해지면 일종의 방향성이 결정된다.

그래서, 두 정점이 간선으로 연결되어 있는 경우, 루트에 가까운 쪽이 "부모"이고 반대쪽에 있는 정점이 "자식"이 된다.
“예제 입력 1”의 상황을 보자.

루트 : 1

1 - 4 : 부모(1) - 자식(4)

4 - 7 : 부모(4) - 자식(7)

3 - 5 : 부모(3) - 자식(5)

그래서, [2, 3, 4, 5, 6, 7]의 부모들은 [4, 6, 1, 3, 1, 4]가 되는 것이다.
트리 구조는 결국 정점과 간선으로 구성된 그래프 구조이다.

그래서, 데이터의 기록 및 탐색/분석은 그래프 알고리즘으로 가능하다.

데이터를 기록하고, DFS/BFS 탐색을 통해 정점(노드)을 방문해 나간다. 이 과정에서 방문 노드의 전단계가 부모 노드가 되기 때문에 이를 기록하면 된다.

문제에서 중요한 3가지 키워드가 있다.
1. 어떤 칸의 안전 거리는 그 칸과 가장 가까운 아기 상어와의 거리.
2. 이동은 인접한 8방향(대각선 포함)이 가능
3. 안전 거리가 가장 큰 칸의 값
임의의 칸에서 아기 상어까지의 최단 거리를 구해야 하는 상황이고, 8방향으로의 이동이 가능하기에 매 칸마다 8방향으로의 간선이 있는 셈이다.

그래서, 모든 칸에서 BFS 탐색을 통해 아기 상어와의 안전 거리를 구하고, 그 중에서 최대값을 찾아내는 문제가 된다.
임의의 지점(빨간 "0")에서 살펴보자.

빨간 "0" 지점에서 BFS 탐색을 통해 8방향을 모두 체크하면, 아기 상어가 있는 지점, "1" 지점까지의 최단 거리(안전 거리)는 "3"이 된다.

이러한 탐색을 모든 칸에 대해서 진행하면서 최대값을 찾아낸다.