[백준] 18126번: 너구리 구구 - BFS (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<Room>[] list)로 방 정보를 저장한다. (방 → 트리)
  • 방 정보 클래스(Room): 방 번호(num, int), 연결된 방과의 길이(length, long)
• 1번방과 연결된 방의 정보를 큐에 저장한다.
• BFS를 사용해 탐색한다.
  • boolean[] visited 배열을 사용하여 방문 여부를 확인한닫.
  • while 반복문을 통해 큐가 빌 때까지 탐색을 계속한다.
  • 큐에서 현재 방 정보(cr)를 꺼낸다.
  • cr.length를 max 변수와 비교하여 최댓값을 갱신한다.
  • cr의 num을 방문 처리합니다.
  • 현재 방(cr.num)과 연결된 모든 이웃 방(nr)을 순회한다.
  • 연결된 방이 아직 방문하지 않은 경우
    • nr에 저장된 길이에 cr.length를 더하여 총 누적 길이를 갱신한다.
    • 갱신된 nr 객체를 큐에 추가한다.
• 최대 길이(max)를 출력한다.

 

3. 최종 코드

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

public class Main {

    static int N; // 방 개수
    static List<Room>[] list; // N+1 크기의 ArrayList 배열로 선언 (방 번호 1~N)
    static Queue<Room> q; // 큐에 방 정보를 넣음
    static long max = 0;

    public static class Room {
        int num;
        long length;

        public Room(int num, long length) {
            this.num = num;
            this.length = length;
        }
    }

    static void BFS() {
        boolean[] visited = new boolean[N+1];
        visited[1] = true; // 방문 여부 확인

        while (!q.isEmpty()) {
            Room cr = q.poll(); // 큐에서 다음 방정보 가져옴
            if (cr.length > max) max = cr.length; // 길이 최댓값 갱신
            visited[cr.num] = true; // 방문 여부 체크
            // 현재 방과 연결된 방을 큐에 넣음
            for (Room nr : list[cr.num]) {
                // 아직 방문하지 않은 방에 현재 길이를 더하여 큐에 저장
                if (!visited[nr.num]) {
                    nr.length += cr.length;
                    q.offer(nr);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        list = new List[N+1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            int lenth = Integer.parseInt(st.nextToken());

            // 양방향 저장
            list[num1].add(new Room(num2, lenth));
            list[num2].add(new Room(num1, lenth));
        }

        // 1번방과 연결된 방의 정보를 큐에 넣음
        q = new LinkedList<>();
        for (Room r : list[1]) {
            q.offer(r);
        }

        BFS();
        System.out.println(max);

        br.close();
    }
}

시간복잡도

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

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

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