728x90
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
// 코드
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
|
import java.util.*;
import java.io.*;
/*
벽인 경우
이전에 부신 적이 없고
방문한 적이 없는 배열이면 방문
벽이 아닌 경우
방문한 적이 없는 배열이면 방문
*/
public class Main{
final static int[][] DIR = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int N, M;
static int[][] arr;
static boolean[][][] visited;
static int bfs() {
Deque<Point> deq = new ArrayDeque<>();
deq.add(new Point(0, 0, 0, 1));
// 벽이 아닌경우 마지막 [0][0]->[0] 마지막 요소가 0인지 1인지는 중요하지 않다
// 그냥 방문을 했는지 안했는지가 중요.
visited[0][0][0] = true;
visited[0][0][1] = true;
while(!deq.isEmpty()) {
Point info = deq.pop();
if(info.row == N-1 && info.col == M-1) return info.cnt;
for(int i=0; i<4; ++i) {
int ny = info.row + DIR[i][0];
int nx = info.col + DIR[i][1];
int breakWall = info.breakWall;
int cnt = info.cnt;
if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if(arr[ny][nx] == 1) { // 벽인경우
if(breakWall == 0 && !visited[ny][nx][1]) { //벽을 부순적 없음
visited[ny][nx][1] = true;
deq.add(new Point(ny, nx, 1, cnt + 1));
}
} else { // 벽이 아닌경우
if(!visited[ny][nx][breakWall]) {
visited[ny][nx][breakWall] = true;
deq.add(new Point(ny, nx, breakWall, cnt + 1));
}
}
}
}
return -1;
}
// main
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new boolean[N][M][2];
for(int i=0; i<N; ++i) arr[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
bw.write(String.valueOf(bfs()));
br.close();
bw.flush();
bw.close();
}
static class Point {
int row, col;
int breakWall; // 0 : 벽을 부순적 없음, 1 : 있음
int cnt;
public Point(int row, int col, int breakWall, int cnt) {
this.row = row;
this.col = col;
this.breakWall = breakWall;
this.cnt = cnt;
}
}
}
|
cs |
반응형