[Programmers] 무인도 여행(Lv.2) - Java

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

프로그래머스

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다.

지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다.

지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다.

지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다.

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다.

지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다.

어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

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

만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

[문제풀이]

간단하게 상, 하, 좌, 우로 연결된 칸들의 합을 구해서 배열에 오름차순으로 저장한뒤 리턴하면 된다.

 

2차원 char배열을 선언해서 값들을 넣어주고

 

visited배열을 이용해서 중복으로 방문하는 경우와(visited[x][y] == true일때)

 

'X'가 아닌 경우 bfs를 이용해서 칸에 적힌 숫자들을 더해주기만 하면 끝

 

import java.util.*;

class Solution {
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static List<Integer> solution(String[] maps){
        List<Integer> answer = new ArrayList<>();
        map = new char[maps.length][maps[0].length()];
        visited = new boolean[map.length][map[0].length];
        for(int i=0;i<maps.length;i++){
            map[i] = maps[i].toCharArray();
        }

        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[i].length;j++){
                if(!visited[i][j] && map[i][j] != 'X'){
                    answer.add(bfs(i, j));
                }
            }
        }

        if(answer.size() == 0){
            answer.add(-1);
        }
        Collections.sort(answer);
        return answer;
    }

    public static int bfs(int x, int y){
        int sum = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            sum += map[cx][cy]-'0';
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length)
                    continue;
                if(!visited[nx][ny] && map[nx][ny] != 'X'){
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return sum;
    }
}