[프로그래머스] 무인도 여행 — BFS

📌 핵심 요약

• 연결 요소별 합계 — 격자에서 상하좌우로 이어진 육지(섬)를 BFS로 묶고, 섬마다 식량의 합을 구하는 문제입니다.
• 거리 BFS vs 집계 BFS — 미로 탈출처럼 거리를 구할 땐 큐에 {r, c, day}를 싣지만, 이 문제는 탐색 밖의 변수 하나에 누적하면 충분합니다.

 

목차

1 문제 소개

Programmers #154540

무인도 여행

지도 최대 100×100 · 각 칸은 X 또는 1~9

난이도: Lv.2

문자열 배열로 주어지는 지도에서 X는 바다, 숫자는 그 칸에서 얻을 수 있는 식량입니다. 상하좌우로 연결된 숫자 칸들이 하나의 무인도를 이룰 때, 각 섬에서 얻을 수 있는 식량의 총합을 오름차순으로 반환해야 합니다. 섬이 하나도 없으면 {-1}을 반환합니다.

풀이 과정

1. 문자열 배열을 char[][] 맵으로 먼저 전부 변환합니다.
2. 이중 루프를 돌며 아직 방문하지 않은 육지 칸을 만나면 BFS를 시작합니다.
3. BFS가 퍼지는 동안 방문하는 칸의 식량을 지역 변수 total에 누적하고, 탐색이 끝나면 그 값이 곧 섬 하나의 식량 합입니다.
4. 섬별 합계를 오름차순 정렬해 int[]로 변환합니다. 리스트가 비어 있으면 {-1}을 반환합니다.

한 문장으로 요약하면 "연결 요소(Connected Component)를 찾고, 각 요소의 값을 합산하라"는 문제입니다. 얼마 전에 풀었던 미로 탈출과 똑같이 격자 BFS인데, 막상 풀어보니 큐에 실어야 하는 정보가 완전히 달랐습니다. 이번 포스트의 핵심은 바로 그 차이입니다.

2 접근: 미방문 육지마다 BFS 한 번씩

전체 구조는 격자 연결 요소 문제의 전형적인 패턴입니다. 바깥에서 이중 루프로 모든 칸을 훑다가, 바다가 아니고 아직 방문하지 않은 칸을 만나면 거기서 BFS를 한 번 돌립니다. BFS 한 번이 섬 하나를 통째로 방문 처리하므로, 같은 섬의 다른 칸에서는 두 번 다시 BFS가 시작되지 않습니다.

 

Java — 탐색 시작 구조

for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (map[i][j] != 'X' && !visited[i][j]) {
            answerList.add(bfs(i, j));  // BFS 1회 = 섬 1개의 식량 합
        }
    }
}

여기서 visited를 클래스 필드로 두는 게 포인트입니다. BFS 호출이 끝나도 방문 기록이 유지돼야 "이미 처리한 섬"을 건너뛸 수 있기 때문입니다. 각 칸은 정확히 한 번씩만 방문되므로 전체 시간 복잡도는 O(N×M)입니다.

3 핵심: 그 값은 누구의 것인가?

처음에는 미로 탈출을 풀던 습관대로 큐에 {행, 열, 값} 형태로 값을 실어 나르려고 했습니다.

그런데 이 문제에서는 그럴 필요가 전혀 없었습니다.

두 방식의 차이를 정리해보니, 기준은 "그 값이 칸마다 다른 답을 가지는가?"라는 질문 하나였습니다.

밖의 변수 = 탐색 전체의 집계

무인도의 식량 합계는 특정 칸의 속성이 아닙니다.

"이 칸의 합계"라는 개념 자체가 없고, 탐색이 끝났을 때 하나만 나오면 되는 값입니다.

이런 값은 노드마다 들고 다닐 이유가 없으니 BFS 바깥의 지역 변수에 누적하면 끝입니다.

 

Java — 두 방식 비교

// [거리 BFS] 값이 칸마다 다름 → 큐에 실어 부모→자식으로 전파
deque.add(new int[]{nr, nc, current[2] + 1});

// [집계 BFS] 값이 탐색 전체에 하나 → 밖의 변수에 누적
total += map[nr][nc] - '0';
deque.add(new int[]{nr, nc});

구분	거리 BFS (큐에 싣기)	집계 BFS (밖에서 누적)
값의 주인	노드 각각	탐색(컴포넌트) 전체
값이 정해지는 방식	부모 값에서 파생 (부모 + 1)	방문한 칸들의 합·개수
답을 읽는 시점	목표 칸을 발견할 때	while 루프 종료 후
대표 문제	미로 탈출 최단거리	무인도 여행 섬 크기·합

💡

상태 설계 판별법

"이 값이 칸마다 다른 답을 가지는가?"를 먼저 물어보세요. 다르면 큐에 싣고, 탐색 끝에 하나만 나오면 되는 값이면 밖에 둡니다. 같은 격자 BFS라도 문제가 묻는 것에 따라 큐에 실어야 할 상태가 달라집니다.

5 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, 1, -1};

    int row, col;
    char[][] map;
    boolean[][] visited;

    public int[] solution(String[] maps) {
        row = maps.length;
        col = maps[0].length();
        map = new char[row][col];
        visited = new boolean[row][col];

        // 1단계: 맵 완성
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map[i][j] = maps[i].charAt(j);
            }
        }

        // 2단계: 미방문 육지마다 BFS
        List<Integer> answerList = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] != 'X' && !visited[i][j]) {
                    answerList.add(bfs(i, j));
                }
            }
        }

        if (answerList.isEmpty()) {
            return new int[]{-1};
        }
        return answerList.stream()
                .sorted()
                .mapToInt(Integer::intValue)
                .toArray();
    }

    public int bfs(int startRow, int startCol) {
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;

        int total = map[startRow][startCol] - '0'; // 시작 칸 식량 포함!

        while (!deque.isEmpty()) {
            int[] current = deque.poll();
            int curRow = current[0];
            int curCol = current[1];

            for (int i = 0; i < 4; i++) {
                int nextRow = curRow + dx[i];
                int nextCol = curCol + dy[i];

                if (nextRow >= 0 && nextCol >= 0 && nextRow < row && nextCol < col
                        && map[nextRow][nextCol] != 'X' && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    total += map[nextRow][nextCol] - '0'; // 방문 처리와 같은 시점에 합산
                    deque.add(new int[]{nextRow, nextCol});
                }
            }
        }
        return total;
    }
}

각 칸을 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N×M)으로 최적입니다. 이 문제는 방문 순서가 결과에 영향을 주지 않아서 DFS로 풀어도 무방하지만, 격자 탐색은 BFS 패턴으로 통일해두는 편이 스택 오버플로 걱정도 없고 익숙해서 BFS를 선택했습니다.

6 마무리

"BFS는 이미 할 줄 안다"고 생각했는데, 미로 탈출의 틀을 그대로 가져왔다가 큐에 실을 필요 없는 값을 실어 나르며 헤맸습니다. 같은 격자 BFS라도 문제가 "몇 번 만에 도달하는가"를 묻는지 "연결된 덩어리의 합이 얼마인가"를 묻는지에 따라 상태 설계가 완전히 달라진다는 걸 몸으로 배운 문제였습니다.

정리하면 이번 문제에서 챙겨갈 것은 세 가지입니다.

• 상태 설계 질문 — 큐에 싣기 전에 "이 값이 칸마다 다른가?"를 먼저 묻는다.
• 초기화 → 탐색 순서 — 자료구조를 다 만들고 나서 그 위에서 탐색을 시작한다.
• 방문·합산 시점 통일 — 큐에 넣는 순간 방문 처리와 합산을 함께 하고, 시작 칸은 루프 밖에서 미리 더한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.