[프로그래머스 Level.2] 무인도 여행 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 무인도 여행

 

 

 

문제 설명

 

 

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

 

지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다.

 

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

 

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

 

---

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

 

---

 

입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

 

---

입출력 예 설명

 

입출력 예 #1

 

위 문자열은 다음과 같은 지도를 나타냅니다.

 

 

연결된 땅들의 값을 합치면 다음과 같으며

 

 

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

 

 

 

 

입출력 예 #2

 

위 문자열은 다음과 같은 지도를 나타냅니다.

 

 

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    char[][] map;
    boolean[][] visited;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    public int[] solution(String[] maps) {
        int[] answer = {};
        
        map = new char[maps.length][maps[0].length()];
        visited = new boolean[maps.length][maps[0].length()];
        
        ArrayList<Integer> resultList = new ArrayList<>();
        
        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[0].length; j++) {
                if(map[i][j] != 'X'  && !visited[i][j]) 
                    resultList.add(bfs(i, j)); 
            }
        }
        
        if(resultList.size() == 0) return new int[] {-1};
        
        answer = new int[resultList.size()];
                       
        Collections.sort(resultList);
                                                                
        for(int i=0; i<resultList.size(); i++) {
            answer[i] = resultList.get(i);
        }
        
        return answer;
    }
                                                                
    public int bfs(int x, int y) {
        int sum = 0;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x, y, map[x][y] - '0'});
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
        
            sum += now[2];
            
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if(nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length && !visited[nx][ny] && map[nx][ny] != 'X') {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny, map[nx][ny] - '0'});
                }
            }
        }
        
        return sum;
    }
}

 

풀이

1. maps를 좌표로 만들고 전체 좌표를 for문을 돌리면서 해당 좌표의 값이 'X'가 아니라면 완전탐색 bfs(너비 우선 탐색)를 이용하여 숫자들끼리 붙어있는 좌표를 구하여 값들을 더하고 해당 좌표를 방문했던 곳으로 표시하여 모든 좌표를 탐색하면 된다.
2. 우선 String배열 maps를 직관적이게 좌표로 나타내기 위해 char형 2차원 배열 map을 생성하고 maps를 for문을 돌리면서 toCharArray()를 이용하여 char형 배열로 변환하여 map에 모두 담아주도록 한다.
3. 숫자로 되어있는 해당 좌표를 중복하여 방문하지 않기 위해 체크할 수 있도록 boolean형 2차원 배열 visited를 생성하고 좌표를 상하좌우로 한 칸씩 이동할 수 있도록 int형 배열 dx와 dy를 만든다.
4. 붙어있는 숫자 좌표(하나의 무인도 땅)들의 합을 구해 담을 수 있도록 ArrayList를 생성한다.
5. map의 전체 좌표를 for문을 돌면서 map의 좌표가 'X'가 아니면서 방문하지 않았다면 bfs()를 통해 붙어있는 좌표를 모두 탐색하여 합을 구해 ArrayList에 담아준다.
6. map을 전부 확인했음에도 ArrayList의 크기가 0이라면 무인도가 없는 것이므로 {-1}을 반환한다.
7. ArrayList가 0이 아니라 무인도가 존재한다면 Collections.sort()를 이용하여 ArrayList를 오름차순 정렬한 후에 for문을 돌려 answer에 순서대로 담고 반환한다.
8. bfs()에서는 우선 붙어있는 숫자 좌표(무인도)들의 값들을 전부 더해주기 위해 int형 변수 sum을 선언하여 0으로 초기화하고 좌표와 해당 좌표의 값을 담기 위해 int형 배열을 선언타입으로 하는 Queue를 생성한다.
9. 그리고 Queue에 현재 map의 좌표인 {x, y map[x][y]}를 Queue에 담아주고 visited[x][y]를 true로 변경한다.
10. 이제 Queue가 빌 때까지 while문을 돌면서 poll()을 이용해 Queue의 값을 꺼내고 해당 값(map[x][y])를 sum에 더해준다.
11. 그리고 dx와 dy를 이용하여 상하좌우 한칸씩 이동한 좌표들이 map의 좌표 범위를 벗어나지 않고 해당 map의 값이 숫자이고 방문하지 않았던 곳이라면 Queue에 담아주고 visited를 true로 한다.
12. 이렇게 while문을 반복하여 진행하고 빠져나오면 연결된 숫자 좌표(무인도)들의 값인 sum을 구할 수 있다.