프로그래머스 Lv2. 154540 - 무인도 여행

프로그래머스 Lv2. 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 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

입출력 예

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

 

방법

1. 각 위치를 x,y로 두고 한칸씩 이동하며 x가 아니고 방문하지 않은 위치를 기준으로 dfs를 실행한다.

2. dfs 함수를 만들어 상하좌우를 돌며 방문하지 않고 해당 위치의 값이 숫자인 곳에서 다시 dfs를 실행한다.

3. return 값으로 해당 위치의 숫자를 받아 더한다.

4. dfs를 완료하면 1번을 반복하며 얻은 값을 리스트에 저장한다.

5. 리스트에 아무값도 없다면 -1을 추가해주고 리스트의 값을 배열로 바꾸어 출력한다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int[] answer = {};
        ArrayList<Integer> list = new ArrayList();
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        
        // 한칸씩 이동하며 해당 위치의 값이 X가 아니고 방문하지 않은 곳이면 dfs실행
        for (int i = 0; i < maps.length; i++){
            for (int j = 0; j < maps[0].length(); j++){
                if (maps[i].charAt(j) != 'X' && visited[i][j] == false){
                    list.add(dfs(maps, visited, j, i));
                }
            }
        }
        
        // 리스트를 오름차순 정렬
        Collections.sort(list);
        
        // 리스트에 값이 없다면 -1을 넣어줌
        if (list.size() == 0){
            list.add(-1);
        }
        
        // 배열로 바꾸어 리턴
        return list.stream().mapToInt(i -> i).toArray();
    }
    
    // dfs 메소드 생성
    public int dfs(String[] maps, boolean[][] visited, int x, int y){
    	// 상하좌우를 탐색하기 위해 미리 방향 배열 생성
        int[][] direction = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        
        int sum = 0;
        
        // 탐색 범위를 벗어나면 리턴
        if (x < 0 || y < 0 || x >= visited[0].length || y >= visited.length ){
            return 0;
        }
        
        // 해당 위치의 값이 X라면 리턴
        if (maps[y].charAt(x) == 'X'){
            return 0;
        }
        
        // 해당 위치를 이미 방문했다면 리턴
        if (visited[y][x] == true){
            return 0;
        }
        
        // 위의 조건에 해당하지 않으면 해당 위치의 방문을 true로 바꾸어줌
        visited[y][x] = true;
        
        // 해당 위치의 값을 더해줌
        sum = (int)maps[y].charAt(x) - '0';
        
        // 상하좌우를 돌며 탐색하여 얻은 값을 더해줌
        for (int[] dir : direction){
            int nextX = x + dir[0];
            int nextY = y + dir[1];
            sum += dfs(maps, visited, nextX, nextY);
        }
        
        // 해당 위치에서 얻을 수 있는 모든 값의 합을 리턴
        return sum;
    }
}