DFS/BFS>게임 맵 최단거리[프로그래머스-JAVA]

📝문제

📝알고리즘

//시작점 (0,0)부터 거리 1로 시작하여
//이를 {x,y,dist}로 큐에 저장하고 방문했다고 기록함
//큐가 빌때까지 다음을 반복
//큐에서 첫 번째 요소를 꺼냄
//꺼낸 요소가 도착 지점이면 거리 dist를 반환
//그렇지 않으면 상하좌우로 탐색해서
//이동 가능하고 방문하지 않은 위치면
//방문했다고 기록하고 dist+1해서 큐에 넣음
//도착 지점에 도달할 수 없으면 -1을 반환

❌틀린 코드

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int n=maps.length;
        int m=maps[0].length;
        
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        boolean[][] visited=new boolean[n][m];
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,0});
        visited[0][0]=true;
        
        while(!queue.isEmpty()){
            int[] now=queue.poll();
            int x=now[0];
            int y=now[1];
            
            if(x==n-1 && y==m-1){
                return answer;
            }
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                
                if(nx>=0 && ny>=0 && nx<n && ny<m && !visited[nx][ny] &&maps[nx][ny]==1){
                    visited[nx][ny]=true;
                    queue.offer(new int[]{nx,ny});
                    answer++;
                }
            }
        }
        return -1;
    }
}

📝틀린 이유

➡️answer가 이동할 때마다 무조건 1씩 증가함. BFS에서는 현재 위치까지의 거리를 따로 관리해야 하는데 answer++로 모든 방향마다 증가하여 방문 횟수가 거리가 되어버림

➡️시작 위치의 거리를 0으로 설정함. (0,0)에서 출발하면 처음 한 칸을 밟는 순간 거리를 1로 시작해야 함

📝수정한 코드

<import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int n=maps.length;
        int m=maps[0].length;
        
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        boolean[][] visited=new boolean[n][m];
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,0,1});
        visited[0][0]=true;
        
        while(!queue.isEmpty()){
            int[] now=queue.poll();
            int x=now[0];
            int y=now[1];
            int dist=now[2];
            
            if(x==n-1 && y==m-1){
                return dist;
            }
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                
                if(nx>=0 && ny>=0 && nx<n && ny<m && !visited[nx][ny] &&maps[nx][ny]==1){
                    visited[nx][ny]=true;
                    queue.offer(new int[]{nx,ny,dist+1});
                }
            }
        }
        return -1;
    }
}

✅거리를 큐에 함께 저장하여 최단 거리를 기록함(이동할 때마다 dist+1을 사용함)

✅시작 거리를 1로 설정함

📌기록하고 싶은 내용

BFS는 가까운 칸부터 탐색하기 때문에 처음 도착한 순간이 최단 거리임