문제

• 2차원 배열 map 이 주어지고 이를 통하여 최단 거리로 갔을 때 가장 빠른 길을 반환한다
  
• 만약 도달 할 수 없는 경우라면 -1 을 반환한다

---

핵심 아이디어

정석적인 그래프 문제 답게 BFS 를 이해한다면 난이도는 어렵지 않다
핵심은 다음과 같다

• 매칸 이동할 때마다 자신의 칸의 +1 로 바꾸어준다
• BFS 가 끝난뒤 맵의 끝에서 아직 1 이라면 -1을 반환한다

시작위치 : 0,0 / 종점 : n-1,m-1 이 고정이기 때문에 어렵지 않게 풀 수 있다

• 방문여부를 위해 따로 배열을 두지 않는다. 이동할 때마다 자신의 칸의 +1 해주기 때문

BFS만 수행하여 최단거리임을 어떻게 아는가?

그림에서 화살표와 같이 BFS 는 깊이우선 탐색이 아닌 너비우선 탐색이다. 즉, 빨간 화살표와 파란 화살표가 만나는 분기점에서 빨간 쪽으로 이동하였을 때 큐에서 순차적으로 뽑아오기 때문에 먼저 도달함을 보장받을 수 있다

문제 풀이

1. 큐에 저장할 포인트 클래스 만들기

class Point{
    int x;
    int y;

    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

2. 전역 변수 지정하기 ( 방향 벡터, 그래프의 크기, 그래프 )

static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int n,m;
static int[][] graph;

3. 함수 설계하기

public static void bfs(){
        // 시작 위치는 항상 1,1
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0));

        while(!queue.isEmpty()){
            // 큐가 비지 않을 때 동안 계속 진행
            Point now = queue.poll(); // 큐에서 하나를 꺼내옴
            int x = now.x;
            int y = now.y;
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 만약 맵의 안에 있으며 움직인 이후의 칸이 1이라면 이동후 바꾸어준다
                if(nx < n && ny < m && nx >= 0 && ny >= 0 && graph[nx][ny]==1){
                    graph[nx][ny] = graph[x][y] + 1; // 현재 칸에서 +1 한 값으로 바꾸어준다
                    if (nx==n && ny==m) return; // 마지막 지점에 도달시 exit
                    queue.add(new Point(nx,ny));
                }
            }
        }
    }

• 0,0 에서 시작하여 큐에서 맵의 범위를 벗어나지 않으면서 방문하지 않은 칸으로 이동 한다
• 이동 위치가 종점이라면 return

---

전체코드

import java.util.*;



class Solution {
    // 매칸 이동할 때마다 자신의 칸의 +1 로 바꾸어 준다
    // bfs 가 끝난뒤 맵의 끝에서 아직 1 이라면 -1을 반환
    
    // 상하좌우 방향 벡터
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int n,m;
    static int[][] graph;
    
    static class Point{
        int x;
        int y;
    
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    public static void bfs(){
        // 시작 위치는 항상 1,1
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0));
        
        while(!queue.isEmpty()){
            // 큐가 비지 않을 때 동안 계속 진행
            Point now = queue.poll(); // 큐에서 하나를 꺼내옴
            int x = now.x;
            int y = now.y;
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 만약 맵의 안에 있으며 움직인 이후의 칸이 1이라면 이동후 바꾸어준다
                if(nx < n && ny < m && nx >= 0 && ny >= 0 && graph[nx][ny]==1){
                    graph[nx][ny] = graph[x][y] + 1; // 현재 칸에서 +1 한 값으로 바꾸어준다
                    if (nx==n && ny==m) return; // 마지막 지점에 도달하였다면 함수를 exit
                    queue.add(new Point(nx,ny));
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        graph = maps;
        bfs();
        answer = graph[n-1][m-1] == 1 ? -1 : graph[n-1][m-1];
        return answer;
    }
}