[프로그래머스/Java] 무인도 여행

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

프로그래머스

 

과정 설명

이 문제는 bfs를 활용하여 문제를 해결하였습니다. 해결 과정을 요약하자면 다음과 같습니다.

1. maps와 똑같은 크기를 가진 boolean 이차원 배열 visited를 만듭니다.

2. maps의 최대 크기는 100 x 100이므로 이중 반복문을 진행해도 시간 초과가 되지 않습니다. 따라서 maps의 구역을 살펴보며 바다가 아니거나 방문한 적이 없다면 해당 지점을 시작으로 bfs를 진행하여 무인도에서 머물 수 있는 시간을 계산합니다.

3. 계산했던 결과들을 배열에 담아 오름차순 정렬 후 반환해줍니다.

 

---

코드

import java.util.*;

class Pair {
    private final int x;
    private final int y;
    
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
}

class Solution {
    
    private static final int ERROR = -1;
    private static final char SEA = 'X';
    
    private final int[] dx = {-1, 0, 1, 0};
    private final int[] dy = {0, 1, 0, -1};
    
    public List<Integer> solution(String[] maps) {
        int rowLen = maps.length;
        int colLen = maps[0].length();
        int[][] board = new int[rowLen][];
        boolean[][] visited = new boolean[rowLen][colLen];
        List<Integer> answer = new ArrayList<>();
        
        for (int i = 0; i < rowLen; ++i) {
            board[i] = new int[colLen];
            
            for (int j = 0; j < colLen; ++j) {
                if (maps[i].charAt(j) == SEA) {
                    board[i][j] = 0;
                } else {
                    board[i][j] = maps[i].charAt(j) - '0';
                }
            }
        }
        
        for (int i = 0; i < rowLen; ++i) {
            for (int j = 0; j < colLen; ++j) {
                if (!isValid(board, visited, i, j)) {
                    continue;
                }
                
                answer.add(bfs(board, visited, i, j));
            }
        }
        
        if (answer.isEmpty()) {
            answer.add(ERROR);
        } else {
            Collections.sort(answer);
        }
        
        return answer;
    }
    
    private int bfs(int[][] board, boolean[][] visited, int row, int col) {
        Queue<Pair> q = new ArrayDeque<>();
        q.offer(new Pair(row, col));
        visited[row][col] = true;
        int days = board[row][col];
            
        while(!q.isEmpty()) {
            Pair pair = q.poll();
            int x = pair.getX();
            int y = pair.getY();
            
            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if(!isValid(board, visited, nx, ny)) {
                    continue;
                }
                
                visited[nx][ny] = true;
                days = days + board[nx][ny];
                q.offer(new Pair(nx, ny));
            }
        }
        
        return days;
    }
    
    private boolean isValid(int[][] board, boolean[][] visited, 
                            int row, int col) {
        return !(row < 0 || col < 0 || row >= board.length || col >= board[0].length) && !visited[row][col] &&
            board[row][col] != 0;
    }
}