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

문제 링크

---

1. 아이디어

지도에서 연결된 땅들의 값의 합을 오름차순으로 정렬하는 문제로 bfs 또는 dfs를 활용해서 해결할 수 있다. 주어진 지도를 순회하며 bfs, dfs로 땅을 발견하면 연결된 땅까지 전부 방문 체크하고 값의 합을 구해 저장한 후 순회가 끝났을 때, 땅이 존재하지 않으면 -1을 담은 배열을, 땅이 존재하면 오름차순으로 정렬해서 return 하면 된다.

---

2. 복잡도

1. bfs

시간복잡도	공간복잡도
$O(NM \log(NM))$	$O(NM)$

$N$ = 격자의 행 수(maps 길이), $M$ = 열 수

2. dfs

시간복잡도	공간복잡도
$O(NM \log(NM))$	$O(NM)$

$N$ = 격자의 행 수(maps 길이), $M$ = 열 수

---

3. 코드

1. bfs [Java][C++]

import java.util.*;

class Solution {

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

    public int[] solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        boolean[][] vis = new boolean[n][m];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maps[i].charAt(j) == 'X' || vis[i][j]) continue;

                int res = bfs(i, j, n, m, maps, vis);
                list.add(res);
            }
        }

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

        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        Arrays.sort(ans);

        return ans;
    }

    static int bfs(int sr, int sc, int n, int m, String[] maps, boolean[][] vis) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        vis[sr][sc] = true;

        int res = maps[sr].charAt(sc) - '0';

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

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

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (maps[nr].charAt(nc) == 'X' || vis[nr][nc]) continue;

                q.offer(new int[]{nr, nc});
                vis[nr][nc] = true;
                res += maps[nr].charAt(nc) - '0';
            }
        }

        return res;
    }
}

#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 n, m;
bool vis[100][100];

int bfs(int sr, int sc, vector<string>& maps) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    vis[sr][sc] = true;

    int res = maps[sr][sc] - '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 (maps[nr][nc] == 'X' || vis[nr][nc]) continue;

            q.push({nr, nc});
            vis[nr][nc] = true;
            res += maps[nr][nc] - '0';
        }
    }

    return res;
}

vector<int> solution(vector<string> maps) {
    n = maps.size();
    m = maps[0].size();
    vector<int> ans;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maps[i][j] == 'X' || vis[i][j]) continue;

            int res = bfs(i, j, maps);
            ans.push_back(res);
        }
    }

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

    sort(ans.begin(), ans.end());
    return ans;
}

2. dfs [Java][C++]

dfs를 활용하면 코드를 좀 더 간결하게 작성할 수 있다. dfs 내부에서 재귀의 반환값을 현재 땅에 더해주면 최종 반환값이 탐색한 전체 땅의 값의 합이 된다.

import java.util.*;

class Solution {

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

    public int[] solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        boolean[][] vis = new boolean[n][m];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maps[i].charAt(j) == 'X' || vis[i][j]) continue;

                int res = dfs(i, j, n, m, maps, vis);
                list.add(res);
            }
        }

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

        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        Arrays.sort(ans);

        return ans;
    }

    static int dfs(int r, int c, int n, int m, String[] maps, boolean[][] vis) {
        vis[r][c] = true;
        int res = maps[r].charAt(c) - '0';

        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 (maps[nr].charAt(nc) == 'X' || vis[nr][nc]) continue;

            res += dfs(nr, nc, n, m, maps, vis);
        }

        return res;
    }
}

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

using namespace std;

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

int n, m;
bool vis[100][100];

int dfs(int r, int c, vector<string>& maps) {
    vis[r][c] = true;
    int res = maps[r][c] - '0';

    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 (maps[nr][nc] == 'X' || vis[nr][nc]) continue;

        res += dfs(nr, nc, maps);
    }

    return res;
}

vector<int> solution(vector<string> maps) {
    n = maps.size();
    m = maps[0].size();
    vector<int> ans;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maps[i][j] == 'X' || vis[i][j]) continue;

            int res = dfs(i, j, maps);
            ans.push_back(res);
        }
    }

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

    sort(ans.begin(), ans.end());
    return ans;
}

---