Review 4 - BFS/DFS/이진탐색/트리 구조 활용

Ⅵ. Tree

1. BFS/DFS

1) BFS/DFS 선택

① 노드 탐색의 방향성이 명확하게 상하 또는 좌우인 경우에 대해서는 각각 DFS와 BFS를 사용하면 된다.

② 탐색 방향이 명확하지 않은 경우, 아래의 기준을 적용한다.

• 인접한 노드를 탐색해야 하는 문제 → BFS
• 노드간 연결 깊이를 따져야하는 문제 → DFS

③ BFS/DFS를 모두 사용해도 되는 문제인 경우, 재귀함수로 구현을 단순화할 수 있는 DFS를 사용한다.

④ 가중치가 없는 그래프에서의 최단 거리를 구하는 문제는 BFS로 풀이한다.

2) 문제 유형

① 인접한 칸으로만 이동하여 도착지까지 도달하는 최단 거리를 구하는 문제

• 가중치가 없는 상황에서 최단 거리를 구하는 문제이므로, BFS를 이용해 풀이한다.
• dx, dy 배열을 이용하여 칸 이동을 구현한다. 이 때, 이동되는 칸이 인덱스를 벗어나지 않는지 반드시 확인해야 한다.

dx = [0, 0, -1, 1] 
dy = [-1, 1, 0, 0]

• 특정 칸까지 도달하는 데 필요한 이동 횟수를 visited 배열에 저장하는 방식으로 풀이한다.

② 트리의 지름

• 트리에 존재하는 임의의 노드에서 최대 거리에 있는 노드는, 반드시 트리의 리프 노드 중 하나이다.
• 최장 거리 문제이므로, DFS로 풀이한다.
• 트리의 지름을 구성하는 경로의 양 끝 노드 중 하나를 찾는 방법은 아래와 같다.
  • 임의의 노드에 대해 DFS를 실행한다.
  • 임의로 선정된 출발 노드로부터 도착 노드까지의 거리를 visited 배열에 저장한다.
  • 해당 노드로부터 가장 거리가 먼 노드가 양 끝 노드 중 하나가 된다.
• 찾은 노드에 대해 DFS를 실행했을 때, 가장 긴 거리가 곧 트리의 지름이 된다.

③ DFS 백트래킹

• 구현
  • 종료 조건(해가 될 수 있는 조건)
  • Pruning 조건
  • DFS 수행 전에 변경된 사항을 DFS 수행 후에 다시 원상 복구
• 적용 기준
  • 특수 기준: 사이클이 포함된 그래프에서 노드 간 연결 깊이가 종료 조건인 경우
  • 일반 기준: Pruning을 적용했을 때, 최적해에 더 빠르게 도달할 수 있는 경우

2. 최적해 이진 탐색

① 정의

• 단조 증가함수 f(x)에 대하여 f(x) ≥ T를 만족하는 x의 최소 값을 찾는 과정이다.
• 단조 감소함수 f(x)에 대하여 f(x) ≥ T를 만족하는 x의 최대 값을 찾는 과정이다.

② 최적해의 위치

• f(x) ≥ T를 만족하는 x의 최소 값을 찾는 문제: start와 end가 교차될 때, start에 해당하는 값이 최적해가 된다.
• f(x) ≥ T를 만족하는 x의 최대 값을 찾는 문제: start와 end가 교차될 때, end에 해당하는 값이 최적해가 된다.

③ 등호의 위치

• 문제의 조건을 만족은 하지만, 최적화가 필요한 경우에 대해 등호를 붙인다.
• 예를 들어, 블루레이 문제에서는 cnt가 M보다 작은 경우에 등호를 붙여야 한다.

if cnt > M: # 블루레이의 사이즈가 작음(문제의 조건을 만족하지 않음)
	start = mid + 1
else: # 블루레이의 사이즈가 큼(문제의 조건은 만족하나, 최적화가 필요함)
	end = mid - 1

④ N X N 행렬(구구단 행렬)의 특징

• K번째에 위치한 숫자는 K보다 클 수 없다.
• i번째 행에서 K보다 작거나 같은 수의 개수는 min(K // i, N)이 된다.

3. 트리 구조 활용하기

① 접근법

• 부모-자식 관계에 놓여있는 노드가 입력으로 주어지는 경우, 이를 간선으로 간주하여 인접 리스트 형태로 나타낸다.
• 트리의 구조를 활용하는 문제는 대부분 BFS/DFS와 관련이 깊다.

② 리프 노드의 개수 구하기

• 어떤 노드의 인접 노드 중 방문하지 않은 노드가 하나도 없다면, 이는 리프노드로 간주할 수 있다.
• 루트 노드가 삭제되는 경우에 대해 리프 노드의 개수를 고정적으로 0으로 출력한다.