[BOJ] 2187. 미로 탐색(BFS).java

#. Problem

https://www.acmicpc.net/problem/2178

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

#. BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ2178_bfs {
 
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int N, M, map[][], dp[][];
    static public class pos{
        int x;
        int y;
        public pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+2][M+2];
        dp = new int[N+2][M+2];
        
        for (int x = 1; x <= N; x++) {
            String str = br.readLine();
            for (int y = 0; y < M; y++) {
                map[x][y+1] = (str.charAt(y)) - '0';
            }
        }
        
        Queue<pos> q = new LinkedList<>();
        q.offer(new pos(1, 1));
        dp[1][1] = 1;
        while(!q.isEmpty()) {
            pos tmp = q.poll();
            // 도착 지점에 도달하면
            if(tmp.x == N && tmp.y == M) break;
            // 인접한 좌표에 길이 있는지 확인
            for (int i = 0; i < 4; i++) {
                int xx = tmp.x + dx[i];
                int yy = tmp.y + dy[i];
                // 해당 지점까지 온 길이가 더 크면 pass
                if(dp[xx][yy] > 1) continue;
                // 벽이면 pass
                if(map[xx][yy] == 0) continue;
                dp[xx][yy] = dp[tmp.x][tmp.y]+1;
                q.offer(new pos(xx, yy));
            }
        }
        
        System.out.println(dp[N][M]);
    }
}
 
// 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸
// DFS : 경로의 수
// BFS : 최단 거리

#. DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ2178_dfs {
 
    static int dx[] = {1, -1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    static int N, M, res = 987654321, map[][];
    static boolean visited[][];
    
    public static void process(int x, int y, int sum) {
        // 도착지점에 도달했을 때 이동거리
        if(x == N-1 && y == M-1) {
            res = Math.min(res, sum);
            return;
        }
        if(map[x][y] < sum) return;
        
        map[x][y] = sum;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            // 범위 넘어가면 패스
            if(xx < 0 || yy<0 || xx>=N || yy>=M) continue;
            // 벽이거나 이미 방문한 곳이라면 pass
            if(map[xx][yy] == 0 || visited[xx][yy]) continue;
            // 지나가지 않은 길이라면 지나가자
            visited[xx][yy] = true;
            process(xx, yy, sum + 1);
            visited[xx][yy] = false;
        }
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for (int x = 0; x < N; x++) {
            String str = br.readLine();
            for (int y = 0; y < M; y++) {
                map[x][y] = ((str.charAt(y)) - '0') * 987654321;
            }
        }
    
        visited[0][0] = true;
        process(0, 0, 0);
        System.out.println(res + 1);
    }
 
}
 
// 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸

DFS는 보통 경로의 수를 구하는 경우 사용되고,

BFS는 보통 최단, 최장 거리를 구하는데 사용된다.

여기서 DFS로 시간초과가 발생하여 해결하지 못 하였다...