무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

접근 방법

BFS와 방문 여부를 체크하며 진행

X인 부분과 이미 방문한 부분은 다시 재탐색할 필요 없으므로, boolean check[][] 배열을 만들어서 방문한 위치를 기록한다.

bfs 함수를 만들어 진행하며, 반환값으로 섬의 넓이를 보낸다.

소스 코드

package programmers.level2.pm154540;

import java.util.*;

class Node{
    int x,y;

    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public int[] solution(String[] maps) {
        List<Integer> list = new ArrayList<>();

        int[][] map = new int[maps.length][maps[0].length()];
        boolean[][] check = new boolean[maps.length][maps[0].length()];

        for(int i=0;i<maps.length;i++){
            String[] str = maps[i].split("");
            for(int j=0;j<str.length;j++){
                if(str[j].equals("X"))
                    map[i][j] = -1;
                else
                    map[i][j] = Integer.parseInt(str[j]);
            }
        }

        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(check[i][j] == false && map[i][j] != -1)
                    list.add(bfs(map, check, i, j));
            }
        }

        int[] answer = list.stream().mapToInt(i->i).toArray();
        Arrays.sort(answer);

        return answer.length == 0 ? new int[]{-1} : answer;
    }

    public int bfs(int[][] map, boolean[][] check, int sx, int sy){
        int sum = 0;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(sx, sy));
        check[sx][sy] = true;
        while(!queue.isEmpty()){
            Node node = queue.poll();
            sum += map[node.x][node.y];
            for(int i=0;i<4;i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                if(0<=nx && nx < map.length && 0 <= ny && ny < map[0].length){

                    if(check[nx][ny] == true)
                        continue;

                    if(map[nx][ny] == -1)
                        continue;

                    check[nx][ny] = true;
                    queue.add(new Node(nx, ny));
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        new Solution().solution(new String[]{"X591X","X1X5X","X231X", "1XXX1"});
    }
}