[Programmers] 154540번 - 무인도 여행 [Java][C++]

문제 링크

---

1. 문제 풀이

지도에 무인도들이 주어져 있고 각 무인도는 섬의 모든 숫자의 합으로 머물 수 있는 날이 정해질 때 지도에서 각 섬별로 머물 수 있는 날을 오름차순으로 구해야 하는 문제다. BFS를 활용해서 지도를 순회하며 섬을 발견하면 해당 섬에 머물 수 있는 날을 계산하며 섬을 방문 처리하는 방식으로 해결했다.

---

2. 코드

1. 풀이 [Java]

import java.util.*;

class Solution {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, 1, 0, -1};

    public int[] solution(String[] maps) {
        int[][] map = init(maps);

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 0) continue;

                int result = bfs(i, j, map.length, map[i].length, map);
                list.add(result);
            }
        }
        list.sort(Comparator.naturalOrder());

        if (list.isEmpty()) {
            return new int[]{-1};
        }
        return listToArr(list);
    }

    static int[][] init(String[] maps) {
        int[][] map = new int[maps.length][maps[0].length()];

        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                char c = maps[i].charAt(j);
                if (c != 'X') map[i][j] = c - '0';
            }
        }

        return map;
    }

    static int bfs(int r, int c, int N, int M, int[][] map) {
        int sum = 0;

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{r, c});

        sum += map[r][c];
        map[r][c] = 0;

        while (!q.isEmpty()) {
            int[] node = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (map[nr][nc] == 0) continue;

                q.offer(new int[]{nr, nc});
                sum += map[nr][nc];
                map[nr][nc] = 0;
            }
        }

        return sum;
    }

    static int[] listToArr(List<Integer> list) {
        int[] arr = new int[list.size()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }

        return arr;
    }
}

2. 풀이 [C++]

#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int bfs(int r, int c, int n, int m, vector<vector<int>>& grid) {
    int sum = 0;

    queue<pair<int, int>> q;
    q.push({r, c});

    sum += grid[r][c];
    grid[r][c] = 0;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc] == 0) continue;

            q.push({nr, nc});
            sum += grid[nr][nc];
            grid[nr][nc] = 0;
        }
    }

    return sum;
}

vector<int> solution(vector<string> maps) {
    vector<vector<int>> grid(maps.size(), vector<int>(maps[0].size()));
    for (int i = 0; i < maps.size(); i++) {
        for (int j = 0; j < maps[0].size(); j++) {
            if (maps[i][j] != 'X') {
                grid[i][j] = maps[i][j] - '0';
            }
        }
    }

    vector<int> ans;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            if (grid[i][j] == 0) continue;

            int res = bfs(i, j, grid.size(), grid[i].size(), grid);
            ans.push_back(res);
        }
    }
    sort(ans.begin(), ans.end());

    if (ans.empty()) {
        return {-1};
    }
    return ans;
}

---