[프로그래머스/Lv. 2] 무인도 여행 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS / DFS

1. 입력받은 1차원 String형 배열을 2차원 int형 배열 grid에 값을 저장한다.

  - 'X'를 입력받은 경우, -1로 값을 설정한다.

  - 숫자를 입력받은 경우, 숫자를 저장한다.

grid[i][j] = maps[i].charAt(j) - '0';

 

 

2. 완전탐색을 통해 2차원 배열 grid를 돌며 방문한 적 없고, X가 아닌 칸 (=-1이 아닌 칸)에 대해 탐색을 수행하며 머물 수 있는 날짜의 수를 구하고, 이 수들을 리스트에 저장한다.

 

3. 만약 머물 수 있는 날짜를 저장한 리스트의 크기가 0이라면, -1만 들어있는 배열을 출력한다.

그게 아닌 경우, 리스트의 값들을 오름차순 정렬한 후, 배열로 변환해 값을 출력하도록 한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1, 1, 0, 0};    // 상하좌우 4방향 탐색용
    static int[] dy = {0, 0, -1, 1};
    
    static int r, c;
    static int[][] grid;
    static boolean[][] visited;
 
    static List<Integer> list = new ArrayList<>();
    
    public int[] solution(String[] maps) {        
        r = maps.length;
        c = maps[0].length();      
        grid = new int[r][c];
        
        for(int i = 0 ; i < r ; i++) {
            for(int j = 0 ; j < c ; j++) {
                if(maps[i].charAt(j) == 'X') {
                    grid[i][j] = -1;
                }
                else {
                    grid[i][j] = maps[i].charAt(j) - '0';
                }
            }
        }
                
        visited = new boolean[r][c];
        
        for(int i = 0 ; i < r ; i++) {
            for(int j = 0 ; j < c ; j++) {
                if(!visited[i][j] && grid[i][j] != -1) {
                    bfs(i, j);
                }
            }
        }
        
        // 출력하기
        if(list.size() == 0) {
            return new int[]{-1};
        }
        
        Collections.sort(list); // 오름차순 정렬하기
        
        // 리스트를 배열로 변환,,
        int[] answer = new int[list.size()];
        int idx = 0;
        for(int i : list) {
            answer[idx++] = i;
        }
        return answer;
    }
    
    private static void bfs(int x, int y) {
        visited[x][y] = true;
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        int sum = grid[x][y];   // 연결된 땅들의 합
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {  // 상하좌우 4방향 탐색
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(canGo(nx, ny)) {
                    visited[nx][ny] = true;
                    sum += grid[nx][ny];    // 연결된 땅들의 합 갱신
                    q.add(new int[] {nx, ny});
                }
            }
        }
        
        list.add(sum);
    }
    
    // [방문 가능한 경우 판별 함수] 격자 범위 내에 있고, 방문한 적 없고, X가 아니면 방문 가능
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && !visited[x][y] && grid[x][y] != -1);
    }
    
    // 격자 범위 내에 있는지 판별용 함수
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < r && 0 <= y && y < c);
    }
}

 

 

➕ 다른 풀이 방식

DFS로도 풀이 가능하다.

 

---

💦 어려웠던 점

- 다들 1차원 배열 입력받은 거 그대로 활용하시는 분이 있나?했더니 다행히(?) 대부분 2차원 배열로 변환해 활용하셨다..

 

 

1회독	2회독	3회독	4회독	5회독
V