BFS ( DFS 로는 실패 )

백준 2178번을 BFS 를 이용해 Java 로 풀어봤다. 처음에는 DFS 로 시도했지만 주어진 예시 하나를 계속 통과하지 못했는데 이건 내가 코드를 잘못 짠 탓인 것 같다... 다른 풀이들을 살펴보니 DFS 로 풀어도 결과는 잘 나오되 시간 초과가 난다고 한다.

DFS 로 풀었을 때의 문제는 결국 상하좌우 어디로 먼저 움직이냐에 따라 시작점에서 가깝되 한참 나중에 방문되는 곳은 count 가 실제 값보다 훨씬 크게 계산되어 나오는 문제였다.

(0,0)에서 출발해서 먼저 밑으로 쭉 간다음에 위로 올라가게 되면 (0,1) 지점은 실제로는 count 가 2여야 하는데,,, 위 그림과 같이 움직이게 될 경우 8로 저장되는 왜곡이 생기는 것이다. 사실 내가 Logic 을 잘못 짠 것 같아서 더 고민해볼까 했지만 그냥 BFS 로 풀면 해결될 것 같아서 그냥 방향을 돌렸다 ㅎ

각 지점마다 알맞은 count 값이 들어갔나 궁금해서 count 값만 저장해줄 int[][] count 를 새롭게 선언해줬다. 모든 예제에 대해서 확인해봤더니 잘 나온다.

좌푯값을 처리해주기 위해서는 배열로 처리할까 하다가 의미가 좀 더 잘 드러나는 코드를 짜고 싶어서 pos 클래스를 새롭게 선언해줬다.

그리고 나는 x, y 로 행과 열을 처리하기보다는 row, col 로 명시해주는 것이 이차원 배열을 다룰 때 헷갈리지 않게 방지해줘서 이렇게 쓰기로 정했다.

아래는 제출한 코드다.

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

class pos{
    int row, col;

    public pos(int row, int col){
        this.row = row;
        this.col = col;
    }
}

public class boj2178 {
    static int N,M;
    static char[][] map;
    static boolean[][] visited;
    static int[][] count;
    static int[] directionRow = { -1, 1, 0, 0}; // 상하좌우 순서
    static int[] directionCol = { 0, 0, -1, 1};
    static Queue<pos> q = new LinkedList<>();

    static void bfs(){
        pos cur = new pos(0,0);
        q.offer(cur);
        visited[0][0] = true;

        while(!q.isEmpty()){
            pos tmp = q.poll();
            int row = tmp.row;
            int col = tmp.col;

            for(int i=0; i<4; i++){
                int newRow = row + directionRow[i];
                int newCol = col + directionCol[i];

                if(newRow<0 || N<=newRow || newCol<0 || M<=newCol)
                    continue;
                if(visited[newRow][newCol] || map[newRow][newCol]=='0')
                    continue;

                count[newRow][newCol] = count[row][col] + 1;
                visited[newRow][newCol] = true;
                q.offer(new pos(newRow, newCol));
            }
        }
    }

    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 = new StringTokenizer(bfr.readLine());

        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];
        count = new int[N][M];

        for(int row=0; row<N; row++){
            String s = bfr.readLine();
            map[row] = s.toCharArray();
        }

        count[0][0] = 1;
        bfs();
        bfw.write(String.valueOf(count[N-1][M-1]));
        bfw.close();
    }
}