문제 출처

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 설명

접근 방법

DFS를 이용하여 풀이했다. 지금까지 갔던 왔던 길의 갯수를 각 칸에 저장하는 visited[]에 왔던 길의 갯수를 저장하고 그와 연결 된 칸들 중 조건을 통과하는 칸을 큐에 삽입한다. 이를 반복하여 최종 칸에 도착한다.

% 하나의 칸에서 갈 수 있는 다른 칸들을 큐에 넣고 그 칸들에서 또 다시 탐색을 해서 큐에 넣는 방식이므로 가장 짧은 경로가 채택이 될 수 밖에 없다.

import java.util.*;

class Solution {
    
    static int[] dx = {1,-1, 0, 0};
    static int[] dy = {0,0, 1, -1};
    static int[][] visited;
    
    public void bfs(int[][] maps, int x, int y){
        Queue<int []> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visited[x][y] = 1;
        
        while(!q.isEmpty()){
            int[] point = q.poll();
            int px = point[0];
            int py = point[1];
            
            for(int i = 0; i<4; i++){
                int nx = px + dx[i];
                int ny = py + dy[i];
                
                if(nx < 1 || nx > maps.length || ny < 1 || ny > maps[0].length || maps[nx-1][ny-1] == 0) continue;
                
                if(maps[nx-1][ny-1] == 1 && visited[nx][ny] == 0){
                    visited[nx][ny] = visited[px][py] + 1;
                    q.offer(new int[]{nx,ny});
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        visited = new int[maps.length + 1][maps[0].length + 1];
        bfs(maps,1,1);
        
        int answer = visited[maps.length][maps[0].length];
        if(answer == 0) return -1;
        
        return answer;
    }
}

Review(코드 동일)

import java.util.*;

class Solution {
    
    static int[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    
    public void bfs(int[][]maps, int x, int y){
        
        Queue<int []> q = new LinkedList<>();
        q.offer(new int[]{x,y});
        visited[x][y] = 1;
        
        while(!q.isEmpty()){
            int[] point = q.poll();
            int bx = point[0];
            int by = point[1];
            
            for(int i = 0; i<4; i++){
                int nx = bx + dx[i];
                int ny = by + dy[i];
                if(nx < 0 || nx >= maps.length || ny < 0 || ny >= maps[0].length || maps[nx][ny] == 0) continue;
                if(visited[nx][ny] == 0){
                    q.offer(new int[]{nx,ny});
                    visited[nx][ny] = visited[bx][by] + 1;
                }
            }
        }
    }
    public int solution(int[][] maps) {
        visited = new int[maps.length][maps[0].length];
        bfs(maps,0,0);
        int answer = visited[maps.length-1][maps[0].length-1];
        return answer == 0? -1 : answer;
    }
}

알게된 점

처음 문제를 접했을 땐, DFS를 이용하여 풀어보았다. 하지만 이는 여러개의 DFS를 호출하게 되어서 시간초과를 일으켰다.

import java.util.*;

class Solution {
    
    static List<Integer> list;
    
    public void dfs(int[][] maps, int count, int x, int y){
    if (x < 1 || y < 1 || x > maps.length || y > maps[0].length || maps[x-1][y-1] == 0) {
        return;
    }
        
        if(x==maps.length && y==maps[0].length){
            list.add(count);
            return;
        }
        
        count++;
        
        maps[x-1][y-1] = 0;
        
        dfs(maps,count,x+1,y);
        dfs(maps,count,x-1,y);
        dfs(maps,count,x,y+1);
        dfs(maps,count,x,y-1);

        maps[x-1][y-1] = 1;
        
    }
    public int solution(int[][] maps) {
        list = new ArrayList<>();
        dfs(maps,1,1,1);
        int answer = maps.length*maps[0].length;
        
        if(list.isEmpty()){
            answer = -1;
        }else{
        for(int i : list){
            answer = Math.min(answer,i);
            }
        }
        return answer;
    }
}

이후 BFS를 이용하여 풀었는데, visited를 만들 생각을 하지 못하여 푸는데 어려움을 겪었다. 추가로 "하나의 칸에서 갈 수 있는 다른 칸들을 큐에 넣고 그 칸들에서 또 다시 탐색을 해서 큐에 넣는 방식이므로 가장 짧은 경로가 채택이 될 수 밖에 없다."에 대해서 이해하는데 생각보다 오래 걸렸다.

% 그림을 그려서 이해해보니 이해가 더 쉬웠다.

참고
https://tmdrl5779.tistory.com/216

문제푼 흔적