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

입출력 예

---

🔎 풀이

지도에서 인접한 무인도를 돌면서 식량의 합을 구하고, 그 합을 배열에 오름차순으로 담아 return 하면 됩니다. 인접한 무인도를 돌아야 하기 때문에 DFS로 풀어야겠다고 생각했습니다.

 

지도가 String 배열로 들어오기 때문에 탐색하기 쉽도록 char형 배열에 저장하였습니다. 그리고 방문을 확인할 수 있도록 boolean형의 2차원 배열 visited를 만들어주고 X인 부분은 true로 바꿨습니다.

혹은 지도를 int 형으로 하고 X인 부분은 -1로 해서 0보다 큰 경우만 방문하는 방식으로 하면 배열을 추가로 더 만들지 않고 풀 수 있을 것 같습니다. 이 경우는 전체 소스코드로 설명하겠습니다!

 

지도를 돌면서 X가 아닌 부분, 즉 visited[i][j]가 false 인 곳만 dfs를 돌면서 식량의 합을 구해주고 그 값을 result arraylist에 넣어줍니다.

 

char[][] mapsArr = new char[maps.length][maps[0].length()];
boolean[][] visited = new boolean[maps.length][maps[0].length()];

for(int i=0; i<maps.length; i++){
    for(int j=0; j<maps[0].length(); j++){
        mapsArr[i][j] = maps[i].charAt(j);
        if(mapsArr[i][j] == 'X'){
            visited[i][j] = true;
        }
    }
}

for(int i=0; i<mapsArr.length; i++){
    for(int j=0; j<mapsArr[0].length; j++){
        if(!visited[i][j]){
            sum = 0;
            dfs(mapsArr, visited, i, j);
            result.add(sum);
        }
    }
}

 

 

DFS 함수는 지도와 방문여부를 확인할 배열(mapsArr / visited), 현재 행(x), 현재 열(y)을 인수로 갖습니다.

 

현재 행과 열을 방문처리 해주고, 식량 값에 현재 식량 값을 더해줍니다. 그리고 동서남북 4방향을 다시 탐색합니다.

만약 현재 행과 열이 배열의 범위를 벗어난다면 return 해주고, 방문한 곳이라면 return 해줍니다.

 

식량의 합을 구하기 위해서 sum 변수를 전역변수로 선언해줬습니다.

 

public void dfs(char[][] maps, boolean[][] visited, int x, int y){
    if(x < 0 || y < 0 || x >= maps.length || y >= maps[0].length)
        return;
    if(visited[x][y])
        return;

    visited[x][y] = true; // 방문처리

    sum += maps[x][y] - '0';

    // 동서남북 확인
    dfs(maps, visited, x, y+1);
    dfs(maps, visited, x, y-1);
    dfs(maps, visited, x+1, y);
    dfs(maps, visited, x-1, y);

}

 

 

지도를 다 돌고 나면 result arraylist에는 인접한 무인도의 식량의 합들이 들어가 있습니다. 그 arraylist의 size가 0이라면 가능한 경우가 없다는 뜻이기 때문에 -1을 return 하고, 아니라면 arraylist를 오름차순 정렬하고 배열로 바꿔 return 하면 됩니다.

 

int[] answer;
if(result.size() == 0){
    return new int[]{-1};
}
else{
    answer = result.stream().mapToInt(Integer::intValue).sorted().toArray();

}

return answer;

---

💡 소스코드

1. visited 배열 사용

import java.util.*;

class Solution {
    
    int sum = 0;
    ArrayList<Integer> result = new ArrayList<>();
    
    public int[] solution(String[] maps) {
        
        char[][] mapsArr = new char[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        
        for(int i=0; i<maps.length; i++){
            for(int j=0; j<maps[0].length(); j++){
                mapsArr[i][j] = maps[i].charAt(j);
                if(maps[i].charAt(j) == 'X'){
                    visited[i][j] = true;
                }
            }
        }
        
        for(int i=0; i<mapsArr.length; i++){
            for(int j=0; j<mapsArr[0].length; j++){
                if(!visited[i][j]){
                    sum = 0;
                    dfs(mapsArr, visited, i, j);
                    result.add(sum);
                }
            }
        }
        
        int[] answer;
        if(result.size() == 0){
            return new int[]{-1};
        }
        else{
            answer = result.stream().mapToInt(Integer::intValue).sorted().toArray();
            
        }
        
        return answer;
    }
    
    public void dfs(char[][] maps, boolean[][] visited, int x, int y){
        if(x < 0 || y < 0 || x >= maps.length || y >= maps[0].length)
            return;
        if(visited[x][y])
            return;
        
        sum += maps[x][y] - '0';
        visited[x][y] = true;
        
        dfs(maps, visited, x, y+1);
        dfs(maps, visited, x, y-1);
        dfs(maps, visited, x+1, y);
        dfs(maps, visited, x-1, y);
        
    }
}

 

2. 지도를 int 배열로 사용

import java.util.*;

class Solution {
    
    int sum = 0;
    ArrayList<Integer> result = new ArrayList<>();
    
    public int[] solution(String[] maps) {
        
        int[][] mapsArr = new int[maps.length][maps[0].length()];
        
        // 바다(X)는 -1로, 무인도는 그 값을 저장
        for(int i=0; i<maps.length; i++){
            for(int j=0; j<maps[0].length(); j++){
                if(maps[i].charAt(j) == 'X'){
                    mapsArr[i][j] = -1;
                }
                else{
                    mapsArr[i][j] = maps[i].charAt(j) - '0';
                }
            }
        }
        
        // 지도의 값이 0보다 큰 부분이 무인도이므로 0보다 큰 부분만 탐색
        for(int i=0; i<mapsArr.length; i++){
            for(int j=0; j<mapsArr[0].length; j++){
                if(mapsArr[i][j] > 0){
                    sum = 0;
                    dfs(mapsArr, i, j);
                    result.add(sum);
                }
            }
        }
        
        int[] answer;
        if(result.size() == 0){
            return new int[]{-1};
        }
        else{
            answer = result.stream().mapToInt(Integer::intValue).sorted().toArray();
            
        }
        
        return answer;
    }
    
    public void dfs(int[][] maps, int x, int y){
        if(x < 0 || y < 0 || x >= maps.length || y >= maps[0].length)
            return;
        // 0보다 작거나 같으면 방문했거나 바다 -> 가지 x
        if(maps[x][y] <= 0)
            return;
        
        sum += maps[x][y];
        maps[x][y] = -1; // 방문 처리
        
        dfs(maps, x, y+1);
        dfs(maps, x, y-1);
        dfs(maps, x+1, y);
        dfs(maps, x-1, y);
        
    }
}