[백준] 18126번: 너구리 구구 - DFS (Java)

1 . 문제 설명

너구리 구구는 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 입구는 1개이고, 입구와 모든 방들은 총 N-1 개의 길로 서로 오고 갈 수 있다. 입구에서 최대한 먼 방에 아이스크림을 숨기려고 한다.

집 입구에서 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구한다.

• 방 개수: 1 ≤ N ≤ 5,000
• 모든 길의 정보 A, B, C: 1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000
• A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C
• 시간 제한: 1초
• 메모리 제한: 1024MB

 

2. 접근 방식

• List<int[]>[] room: N+1 크기의 ArrayList를 사용한다. (인접리스트로 방의 트리 정보 저장)
• N-1 개의 간선 정보를 room 리스트에 저장한다. 무방향이므로 양방향으로 저장한다.
• DFS를 이용한다.
  • 1번 방부터 시작하여 가능한 경로를 탐색하고, 가장 긴 길이를 찾는다.
  • boolean[] visited를 사용하여 방문하지 않은 경로로 재귀 호출한다.

 

3. 최종 코드

import java.io.*;
import java.util.*;

public class Main {

    static int N; // 방 개수
    static List<int[]>[] room; // N+1 크기의 ArrayList 배열로 선언 (방 번호 1~N)
    static long max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        room = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            room[i] = new ArrayList<>();
        }
        
        // N-1 개의 간선 정보 읽기
        for (int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // 무방향이기 때문에 양쪽에 추가
            room[a].add(new int[]{b, c});
            room[b].add(new int[]{a, c});
        }

        // DFS로 탐색
        dfs(1, 0, new boolean[N+1]);

        System.out.println(max);

        br.close();
    }

    static void dfs(int curRoom, long curLength, boolean[] visited) {
        visited[curRoom] = true; // 방문 처리

        if (curLength > max) max = curLength; // 최대 거리 갱신

        for (int[] nextInfo : room[curRoom]) {
            int nextRoom = nextInfo[0];
            int nextLength = nextInfo[1];

            // 아직 방문하지 않은 경우 재귀 호출
            if (!visited[nextRoom])
                dfs(nextRoom, curLength + nextLength, visited);
        }
    }
}

시간복잡도

입력 처리 부분의 시간 복잡도는 $O(N)$

DFS 탐색의 시간 복잡도는 $O(N + (N-1)) = O(N)$

⇒ 전체 알고리즘의 시간 복잡도는 입력 처리와 DFS 탐색을 합쳐 $O(N)$

 

4. 분석 및 참고사항

• 나는 DFS로 풀었지만, BFS로 푸는 것이 더 적절하다.
• 거리 문제일 경우 높은 확률로 BFS 기반 문제이다. BFS로 해결되지 않을 경우 그 다음 방법들을 고려 → 다 익스트라 등
• BFS 접근 방법:
  1. 인접 리스트로 트리 정보 저장
  2. BFS를 통해 1번 노드에서 출발하여 모든 노드 방문
  3. 다음 방문할 노드가 없으면 최장 거리 후보로 기록
  4. BFS 종료 후 최장 거리 출력
• 주의 사항
  • long 자료형 사용 (간선 가중치 최대 10^9)
  • 방문 여부를 체크하여 중복 방문 방지
  • 마지막 노드가 아닌 모든 경로에 대한 최장 거리 갱신