SW Expert Academy의 '탈주범 검거' 문제와 풀이 방식이 동일하다.
BFS의 Level 단계를 파악하는 것이 핵심 포인트! 그래서 파라미터로 time을 넘겨줘야 한다.
우선 문제 파악부터 해보쟈
[문제 요약]
1. N x M 크기의 배열의 미로가 있다.
2. 1은 이동 가능, 0은 이동 불가능을 의미한다.
3. (1,1)에서 출발하여 (N,M)의 위치로 이동할 때, 지나야 하는 최소의 칸 수는~?
4. 칸을 셀 때는, 시작 위치 (1,1)과 도착 위치 (N,M)을 포함해야 한다.
[Input]
1. 행 N, 열 M 입력
2. N x M의 미로가 주어진다. 각 수는 붙어서 입력으로 주어진다.
ㄴ Re : 붙어서 입력 받아지는 숫자들을 분리해서 맵에 넣어주어야 한다.
3. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.
ㄴ Re : 도착 지점으로 무조건 갈 수 있으니 다른 경우는 신경쓰지 말란 소리!
Output은 평범해서 생략. 그냥 최소 시간을 출력하면 된다.
[Key Point]
1. 각 행을 String으로 입력 받고, charAt을 이용하여 아스키 값을 받은 뒤, int형으로 변환!
여기서 주의할 점은, 0은 아스키코드 값으로 '48'이다.
2. DFS가 아닌 BFS로 탐색해야 한다. 이 문제는 BFS로 얼마 만큼의 깊이 까지 들어가야 도착점에 도달하는지를 묻는 문제이다.
[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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
/*
* 백준 2178번, 미로 탐색 문제.
*
* 1. N*M크기의 배열로 표현되는 미로가 있다.
* 2. 미로에서 1은 이동 가능, 0은 이동 불가능을 나타낸다.
* 3. 이 때, (1,1)에서 출발하여 (N,M)으로 이동할 때, 지나야 하는 최소 칸의 수를 구하여라.
*
*
*/
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;
public class boj_2178_miro {
private static int Map[][];
private static boolean visited[][];
private static int N, M;
private static int total;
private static int xx[] = { -1, 1, 0, 0 };
private static int yy[] = { 0, 0, -1, 1 };
public static void bfs(int x, int y,int time) {
visited[x][y] = true;
Queue<Point> Q = new LinkedList<Point>();
Queue<Integer> level = new LinkedList<>();
Q.add(new Point(x, y));
time++;
level.add(time);
while (!Q.isEmpty()) {
int cx = Q.peek().x; // current x
int cy = Q.peek().y; // current y
int Time = (int)level.poll();
Q.poll();
if (cx == N - 1 && cy == M - 1) {
total = Time++;
return;
}
for (int i = 0; i < 4; i++) {
int nx = cx + xx[i]; // next x
int ny = cy + yy[i]; // next y
if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1)
continue;
if (visited[nx][ny])
continue;
if (Map[nx][ny] == 1) {
visited[nx][ny] = true;
Q.add(new Point(nx, ny));
level.add(Time+1);
}
}
}
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
Map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String temp = sc.next();
for (int j = 0; j < M; j++) {
Map[i][j] = (int) temp.charAt(j) - 48;
}
}
bfs(0, 0, 0); // 0,0에서 bfs 시작.
System.out.println(total);
}
}
| cs |
댓글
댓글 쓰기