[BOJ] 2178. 미로 탐색(BFS, DP).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를 사용해야한다.

DFS는 계속 파고 들어가는데, 알고보니 가장 가까운 다른 쪽이 최소인 경우가 있을 수 있기 때문에

이런 문제에서는 비효율적이다. 

실제로 DFS로 풀어봤는데 시간초과가 나버린다..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

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));         // 시작점은 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;                 // 이전 길까지의 칸 수 + 1                 dp[xx][yy] = dp[tmp.x][tmp.y]+1;                 q.offer(new pos(xx, yy));             }         }                  System.out.println(dp[N][M]);     } } Colored by Color Scripter

cs