👀 문제
https://www.acmicpc.net/problem/2206
👊 도전
1. 설계
- (N, M)까지의 최단거리를 구해야하므로 BFS를 사용한다.
- map[i][j]==1(벽)이고 부순 적이 없다면 부순다.
- (N, M)에 도착할 수 있다면 최단경로를 출력, 아니라면 -1을 출력한다.
2. 구현 (성공 코드)
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
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
class Node{
int x;
int y;
int way;
int drill;
public Node(int x, int y, int w, int d) {
this.x=x;
this.y=y;
this.way=w;
this.drill=d;
}
}
public class Main {
static int n, m, answer;
static int[][] map, visit;
public static int bfs() {
Queue<Node> q=new LinkedList<>();
q.offer(new Node(1,1,1,0));
visit[1][1]=0;
int[] dotX= {0,0,-1,1};
int[] dotY= {-1,1,0,0};
while(!q.isEmpty()) {
Node node=q.poll();
if(node.x==n&&node.y==m) return node.way;
for(int i=0;i<4;i++) {
int xx=node.x+dotX[i];
int yy=node.y+dotY[i];
if(xx<=0||xx>n||yy<=0||yy>m) continue;
if(node.drill>=visit[xx][yy]) continue;
if(map[xx][yy]==0) {
visit[xx][yy]=node.drill;
q.offer(new Node(xx,yy,node.way+1,node.drill));
}
else if(map[xx][yy]==1&&node.drill==0){
visit[xx][yy]=1;
q.offer(new Node(xx,yy,node.way+1,1));
}
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
map=new int[n+1][m+1];
for(int i=1;i<=n;i++) {
String str=scan.next();
for(int j=1;j<=m;j++) {
map[i][j]=str.charAt(j-1)-'0';
}
}
visit=new int[n+1][m+1];
for(int i=0;i<=n;i++) {
Arrays.fill(visit[i], Integer.MAX_VALUE);
}
System.out.println(bfs());
}
}
3. 결과
🤟 성공 🤟
4. 설명
- BFS를 구현한다
- 최단거리를 구해야하므로 BFS 탐색을 사용한다.
- Queue에 넣을 클래스 Node를 생성한다. x, y는 위치, way는 map[x][y]까지의 최단거리, drill은 부순 횟수이다.
- visit는 부순 횟수를 저장한다. 0, 1의 값을 가져야하므로 Integer.MAX_VALUE로 초기화한 후 사용한다.
- (1,1)을 큐에 넣고 while문을 실행한다. 상하좌우 움직일 수 있는 좌표를 xx, yy에 저장하고 범위가 넘어가지는 않는지, visit[xx][yy]가 현재보다 크진 않는지 확인한다. 다음에 방문할 xx, yy에서 부순 횟수가 현재보다 더 크다면 말이 되지 않으므로 패스한다.
- map[xx][yy]==0이면 벽이 아니므로 way+1만 해준다.
- map[xx][yy]==1이라면 부순 횟수가 있는지 확인 후, 없다면 부수고 지나간다.
- 큐에 n, m이 나오면 방문할 수 있다는 뜻이므로 그때의 way를 리턴한다.
- n, m방문 없이 큐가 비어서 마지막 리턴문까지 가면 (N,M)에는 방문할 수 없다는 뜻이므로 -1을 리턴한다.
👏 해결 완료!
참고
- [백준2206]벽 부수고 이동하기(Java,BFS) https://kim6394.tistory.com/201