백준 6118번 문제는 "숨바꼭질" 문제로, 최단 거리를 구하는 문제입니다. N개의 노드가 있고, 각 노드는 양방향으로 연결되어 있습니다. 특정 노드에서 시작하여 다른 모든 노드로의 최단 거리를 구하고, 가장 먼 노드까지의 거리와 그러한 노드의 개수를 출력하는 문제입니다.
이 문제를 해결하기 위한 알고리즘은 BFS(Breadth-First Search)를 사용했습니다. BFS는 너비 우선 탐색으로, 그래프 탐색 알고리즘 중 하나입니다. 이 문제에서 BFS를 선택한 이유는 최단 거리를 구해야 하기 때문입니다. BFS는 시작 노드로부터 거리가 가까운 노드부터 탐색하기 때문에, 최단 거리를 효율적으로 찾을 수 있습니다. DFS(Depth-First Search)를 사용하면 최단 거리가 아닌 경로를 먼저 탐색할 수 있으므로 적합하지 않습니다.
단계별 접근 방법 및 로직:
-
입력: 노드의 개수 N과 연결된 노드 쌍의 개수 M을 입력받습니다. 그리고 각 노드간의 연결 정보를 인접 리스트 형태로 저장합니다. 인접 리스트는 그래프를 효율적으로 표현하는 방법 중 하나로, 각 노드에 연결된 노드들을 리스트로 관리합니다.
-
BFS 탐색: 1번 노드(문제에서 시작 노드는 1번으로 지정)부터 BFS 탐색을 시작합니다. 큐(Queue) 자료구조를 사용하여 탐색을 진행합니다. 큐에 노드를 추가하고, 큐에서 노드를 꺼내면서 인접 노드들을 방문합니다. 각 노드에 대한 최단 거리를 저장하는
dist배열을 사용합니다. 방문한 노드는visited배열을 통해 관리합니다. -
최대 거리 및 노드 개수 계산: BFS 탐색이 완료되면,
dist배열에서 최대 거리를 찾습니다. 최대 거리를 가진 노드의 개수를 카운트합니다. -
출력: 첫 번째는 1번부터 최대로 떨어져있는 노드의 번호를(만약 거리가 같은 노드가 여러개면 가장 작은 노드 번호를 출력), 두 번째는 그 노드까지의 거리를, 세 번째는 그 노드와 같은 거리를 갖는 노드의 개수를 출력합니다.
알고리즘 특징 및 장단점:
- BFS (Breadth-First Search):
- 장점: 최단 경로를 보장합니다. 계층적인 탐색을 통해 효율적으로 최단 거리를 찾습니다.
- 단점: 메모리 사용량이 DFS보다 클 수 있습니다. 큐에 많은 노드가 저장될 수 있습니다. 하지만 이 문제의 경우, 노드의 수가 충분히 작아 메모리 문제는 발생하지 않습니다.
코드 (Python):
import java.io.*;
import java.util.*;
public class b6118 {
// 입력을 위한 BufferedReader와 출력을 위한 BufferedWriter 선언
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N, M; // N: 노드 개수, M: 간선 개수
static ArrayList<ArrayList<Integer>> graph; // 인접 리스트로 그래프 표현
static int[] dist; // 각 노드까지의 거리 저장 배열
static int MAX_INTEGER = 20000000; // 초기 거리 값 (충분히 큰 값)
static int max_dist; // 최장 거리 저장 변수
// 입력 처리 메서드
static void input() throws IOException {
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]); // 노드 개수 입력
M = Integer.parseInt(input[1]); // 간선 개수 입력
// 그래프 초기화 (0번 인덱스는 사용하지 않음)
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
dist = new int[N + 1]; // 거리 배열 초기화
// 간선 정보 입력 및 인접 리스트 저장
for (int i = 0; i < M; i++) {
input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
graph.get(start).add(end);
graph.get(end).add(start);
}
}
// BFS 수행하여 최단 거리 계산
static void bfs() {
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 시작 노드는 1번
Arrays.fill(dist, MAX_INTEGER); // 모든 거리를 큰 값으로 초기화
dist[1] = 0; // 시작 노드의 거리는 0
max_dist = 0; // 최장 거리 초기화
while (!queue.isEmpty()) {
int start = queue.poll(); // 현재 노드 가져오기
// 현재 노드와 연결된 모든 노드 탐색
for (int node : graph.get(start)) {
if (dist[node] > dist[start] + 1) { // 더 짧은 거리 발견 시 갱신
dist[node] = dist[start] + 1;
max_dist = Math.max(max_dist, dist[node]); // 최장 거리 업데이트
queue.add(node); // 다음 탐색을 위해 큐에 추가
}
}
}
}
// 결과 출력 메서드
static void result() throws IOException {
int count = 0; // 최장 거리에 있는 노드 개수
int num_first = 0; // 최장 거리를 가지는 첫 번째 노드
for (int i = 1; i <= N; i++) {
if (dist[i] == max_dist) { // 최장 거리 노드 찾기
count++;
if (num_first == 0) { // 첫 번째로 등장한 노드 저장
num_first = i;
}
}
}
// 첫 번째 최장 거리 노드, 거리, 해당 거리의 노드 개수 출력
bw.write(num_first + " " + max_dist + " " + count);
}
public static void main(String[] args) throws IOException {
input(); // 입력 처리
bfs(); // BFS 수행
result(); // 결과 출력
bw.flush(); // 출력 버퍼 비우기
bw.close(); br.close(); // 리소스 닫기
}
}
이 코드는 입력받은 그래프를 이용하여 BFS를 수행하고, 최대 거리와 그 거리에 해당하는 노드의 개수를 출력합니다. 주석을 통해 각 부분의 역할을 명확히 설명했습니다. dist 배열을 사용하여 각 노드까지의 최단 거리를 저장하고, max_dist와 count 변수를 사용하여 최대 거리와 그에 해당하는 노드의 개수를 관리합니다.
