[Programmers] 게임 맵 최단거리

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

프로그래머스

문제 설명

기본적인 DFS/BFS 문제이다. 다만 효율성 때문에 BFS를 사용해야 한다. DFS로 해결하면 효율성 테스트 케이스를 통과하지 못한다.

코드

BFS

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    private int targetX;
    private int targetY;
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] maps) {
        targetX = maps.length;
        targetY = maps[0].length;
        
        int[][] borderedMaps = bordering(maps);
        
        return bfs(borderedMaps);
    }
    
    private int bfs(int[][] maps) {
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(1, 1, 1));
       
        while(!q.isEmpty()) {
            Position p = q.poll();
            
            if (p.x == targetX && p.y == targetY) {
                return p.distance;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                
                if (maps[nx][ny] == 1) {
                    // 재방문 회피를 위해 0으로 변경
                    maps[nx][ny] = 0;
                    q.offer(new Position(nx, ny, p.distance + 1));
                }
            }
        }
        
        return -1;
    }
    
    static class Position {
        public int x;
        public int y;
        public int distance;
        
        public Position(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
    
    // 맵을 0으로 감싸서 배열 초과 오류에 대한 메인 로직 간소화
    private int[][] bordering(int[][] maps) {
        int[][] result = new int[maps.length + 2][maps[0].length + 2];
        
        for (int i = 1; i <= maps.length; i++) {
            for (int j = 1; j <= maps[0].length; j++) {
                result[i][j] = maps[i - 1][j - 1];
            }
        }
        
        return result;
    }
}

DFS (효율성 실패)

class Solution {
    private int targetX;
    private int targetY;
    private int answer = Integer.MAX_VALUE;
    private boolean[][] visited;
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] maps) {
        targetX = maps.length;
        targetY = maps[0].length;
        
        int[][] borderedMaps = bordering(maps);
        visited = new boolean[borderedMaps.length][borderedMaps[0].length];
        
        dfs(borderedMaps, 1, 1, 1);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    private void dfs(int[][] maps, int n, int m, int distance) {
        if (n == targetX && m == targetY) {
            answer = Math.min(answer, distance);
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = n + dx[i];
            int ny = m + dy[i];
            
            if (!visited[nx][ny] && maps[nx][ny] == 1) {
                visited[nx][ny] = true;
                dfs(maps, nx, ny, distance + 1);
                visited[nx][ny] = false;
            }
        }
    }
    
    private int[][] bordering(int[][] maps) {
        int[][] result = new int[maps.length + 2][maps[0].length + 2];
        
        for (int i = 1; i <= maps.length; i++) {
            for (int j = 1; j <= maps[0].length; j++) {
                result[i][j] = maps[i - 1][j - 1];
            }
        }
        
        return result;
    }
}