프로그래머스 | LV.2 무인도 여행 - DFS or BFS 문풀 (Java)

⬛ 프로그래머스 | LV.2 무인도 여행 - DFS or BFS 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

이 문제의 경우 DFS로 풀든, BFS로 풀든 시작점에서 갈 수 있는 유효한 무인도를 모두 돌면서 누적한 값을 계속 List에 담아주면서 처리하고 그걸 오름차순 정렬하여 반환하면 되는 문제이다. 나는 BFS로 풀었다.

1) board[][]에 String으로 들어오는 지도 정보를 char 형으로 변환해주고 이떄 flag 를 걸어서 만약 X아닌 값이 하나도 안나온다면 BFS 순회도 전에 -1 리턴하도록 한다.

 

2) 이중 for문 돌면서 방문 전이면서 ‘X’ 가 아닌 좌표값에 대해 BFS를 순회한다.

 

3) BFS는 내부적으로 시작점부터 다음의 유효한 무인도에 대한 좌표로만 방문하도록 조건을 걸어두었으므로 인접한 정점 모두 순회하며 누적한 값을 리턴하도록 한다.

 

4) 리턴한 값을 List에 담고 sort 하면 된다.

 

💚 제출 코드

import java.util.*;
class Solution {
    private static char[][] board;
    private static int N, M;
    private static boolean[][] visited;
    //4방향
    private static int[] dx = {0, 0, 1, -1};
    private static int[] dy = {1, -1, 0, 0};
    
    //BFS
    private int BFS(int x, int y){
        Queue<int []> Q= new LinkedList<>();
        visited[x][y] = true;
        Q.offer(new int[] {x, y});
        int answer = Character.getNumericValue(board[x][y]);
        
        while(!Q.isEmpty()){
            int[] cur = Q.poll();
            for(int k=0; k<4; k++){
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if(nx < 0 || ny <0 || nx >=N || ny>= M || board[nx][ny] == 'X') continue;
                if(visited[nx][ny] == true) continue;
                
                answer += board[nx][ny] - '0';
                visited[nx][ny] = true;
                Q.offer(new int[] {nx, ny});
            }
        }
        return answer;
    }
    
    //솔루션 함수 
    public List<Integer> solution(String[] maps) {
        List<Integer> answer = new ArrayList<>();
        
        N = maps.length;
        M = maps[0].length();
        
        board = new char[N][M];
        visited = new boolean[N][M];
        
        boolean flag = false;
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                board[i][j] = maps[i].charAt(j);
                if(board[i][j] != 'X') flag = true;
            }
        }
        
        if(!flag) {
            answer.add(-1);
            return answer;
        } 
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visited[i][j] && board[i][j] != 'X'){
                    answer.add(BFS(i, j));
                }
            }
        }
        
        Collections.sort(answer);
        
        return answer;
    }
}

💚회고 & 시간복잡도

이 문제는 전형적인 DFS, BFS 문제이다. 시간은 20분 정도 걸렸다. 시간복잡도의 경우 이중 순회 대상인 maps의 길이가 최대 100 X 100 이기 때문에 크게 문제없이 시간 내에 동작할 것으로 봤다.