[Level2] 무인도 여행 (JAVA)

무인도 여행 문제 링크

정답 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int[] solution(String[] maps) {
        List<Integer> result = new ArrayList<>();
        int[] dx = { 1, 0, -1, 0 };
        int[] dy = { 0, 1, 0, -1 };
        boolean[][] check = new boolean[maps.length][maps[0].length()];

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                if(maps[i].charAt(j) == 'X' || check[i][j]) continue;
                Queue<Point> queue = new LinkedList<>();
                queue.add(new Point(i,j));
                check[i][j] = true;
                int sum = 0;
                while(!queue.isEmpty()) {
                    Point p = queue.poll();
                    sum += (maps[p.x].charAt(p.y) - '0');

                    for(int dir = 0; dir < 4; dir++) {
                        int nx = p.x + dx[dir];
                        int ny = p.y + dy[dir];

                        if(nx < 0 || ny < 0 || nx >= maps.length || ny >= maps[0].length()) continue;
                        if(maps[nx].charAt(ny) == 'X' || check[nx][ny]) continue;
                        check[nx][ny] = true;
                        queue.add(new Point(nx, ny));
                    }
                }
                result.add(sum);
            }
        }
        if(result.size() == 0) result.add(-1);
        return result.stream()
                    .mapToInt(Integer::intValue)
                    .sorted()
                    .toArray();
    }
}
class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

풀이 해설

bfs 혹은 dfs로 쉽게 풀 수 있는 문제다.
나는 더 익숙한 bfs로 풀었다.

1. X가 아닌 좌표를 찾는다.
2. bfs를 이용해서 탐색한 칸의 값을 더한다.
3. 더 이상 탐색할 수 있는 칸이 없다면 result에 더한 값을 넣는다.
4. 만약 result에 요소가 없다면 탐색할 수 있는 칸이 한 칸도 없다는 뜻으로 -1 을 넣어준다.