BFS로 최단 경로 찾기

일단 첫 번째로 최단 경로를 구할 때는 DFS보다 BFS를 이용한다는 사실조차 제대로 몰라 먼저 DFS로 덤볐다가 뒤늦게 BFS로 풀어야 한다는 것을 알게됐다.
정말 넘어야할 산이 너무나도 많다...

한 번에 여러 칸 움직이기

일단 이 문제가 앞서 풀었던 간단한 BFS문제들과 다른 점은, 한 번 이동할 때 여러 칸을 움직일 수 있는 가능성이 있다는 것이다. 그런데 여러 칸도 무한대로 많은 칸을 움직일 수 있는 것이 아니라 입력으로 받게 될 수만큼만 움직일 수 있다는 점이다.

이 문제를 어떻게 해결할지 처음에 많이 고민하고 내 나름대로 로직을 짰지만 개판이었고 정답을 내지도 못했다.
생각보다 해결방법이 너무나도 간단해서 가슴이 아팠다...
어째서 나는... 이렇게 멍청한 것일까 ㅠ...

for(int i=0; i<4; i++){
                for(int j=1; j<=K; j++){
                    int newRow = curRow + directionRow[i]*j;
                    int newCol = curCol + directionCol[i]*j;
                    ...

주어진 숫자 K만큼 움직일 수 있다면 1칸의 움직임을 1부터 K까지 곱해가면서 탐색해주면 쉽게 해결이 가능했다!

방문의 필요성

모든 지점을 다 방문해야만 이미 방문된 지점도 더 작은 값으로 다시 계산할 수 있다는 생각에서 벗어나지 못해서 방문 필요성을 if문으로 확인할 때 이미 계산된 칸도 다시 방문하도록 조건 설정을 했다.
내가 했던 생각은 만약 재차 방문해서 더 작은 값으로 계산될 수 있다면, 여러 번 방문을 하더라도 반드시 해줘야하는 거 아닌가? 라는 생각이었고 틀린 생각이었다.

왜냐하면 DFS를 사용할 경우에는, 일단 쭉 깊게 파고 들어가니까 다른 경우의 수가 존재할 것을 고려해서 재차 방문도 할 수 있겠지만 애초에 BFS를 사용함으로써 가장 먼저 방문된 경우가 최단 시간을 보장해주는 것 아니겠는가? 쭉 깊게 들어가는 것이 아니라, 한 칸씩 한 칸씩 뻗어나가니까 당연히 먼저 만나면 그게 가장 최단 시간이란 것을 깨닫지 못한 무지함이었던 것이다.

이러한 원리를 통해 목적지점을 만나게 되면 그 라인에서 바로 return 을 때려주면 어차피 우리가 원하는 결과는 이미 계산된 것이다. 그래서 if문을 통해 break를 걸어주면 되는 것이다.

바로 이 원리를 깨닫지 못해서 내 코드의 로직은 분명히 맞고 결과도 맞는데 왜 자꾸 시간 초과, 메모리 초과가 나는 것인가!! 하며 분노의 재채점을 12번도 더 했고 결국 채점 페이지가 2 페이지를 넘어가게 됐다 ㅎ...

위의 재방문에 대한 조건 하나만 제대로 걸어주니까 바로 통과했다.

아래는 내가 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj16930 {
    static int N,M,K;
    static char[][] map;
    static int[][] visited;
    static int startRow, startCol, endRow, endCol;
    static int[] directionRow = { -1, 1, 0 ,0 }; // 상하좌우
    static int[] directionCol = { 0, 0, -1, 1};

    static void bfs(){
        Queue<int []> q = new LinkedList<>();
        q.add(new int[]{ startRow, startCol });

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int curRow = cur[0];
            int curCol = cur[1];

            for(int i=0; i<4; i++){
                for(int j=1; j<=K; j++){
                    int newRow = curRow + directionRow[i]*j;
                    int newCol = curCol + directionCol[i]*j;

                    if(newRow>=1 && newRow<=N && newCol>=1 && newCol<=M && map[newRow][newCol]=='.'){
                        if(visited[newRow][newCol]==0){
                            visited[newRow][newCol] = visited[curRow][curCol] + 1;
                            if(newRow==endRow && newCol==endCol)
                                return;
                            q.add(new int[]{newRow, newCol});
                        }
                        else if(visited[newRow][newCol]<=visited[curRow][curCol])
                            break;
                    }
                    else
                        break;
                }
            }
        }
    }

    public static void main(String args[]) throws IOException{
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());

        map = new char[N+1][M+1];
        visited = new int[N+1][M+1];

        for(int i=1; i<=N; i++){
            String s = bfr.readLine();
            for(int j=1; j<=M; j++)
                map[i][j] = s.charAt(j-1);
        }

        stk = new StringTokenizer(bfr.readLine());
        startRow = Integer.parseInt(stk.nextToken());
        startCol = Integer.parseInt(stk.nextToken());
        endRow = Integer.parseInt(stk.nextToken());
        endCol = Integer.parseInt(stk.nextToken());

        bfs();
        visited[endRow][endCol] = visited[endRow][endCol]==0 ? -1:visited[endRow][endCol];
        bfw.write(String.valueOf(visited[endRow][endCol]));
        bfw.close();
    }
}

---

오늘 배운 것

BFS는 DFS와 다르다!! BFS의 경우에는 먼저 도착한 것이 최단 시간을 갖는 경로인 것이다! 따라서 이미 값이 계산된 지점은 다시 방문해줄 필요가 없다!