미로 탐색(2178)
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
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] nm;
static boolean[][] v;
static int[][] cnt;
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
nm = new boolean[n][m];
v = new boolean[n][m];
cnt = new int[n][m];
for(int i = 0; i < n; i++) {
char[] tmp = br.readLine().toCharArray();
for(int j = 0; j < m; j++) {
if(tmp[j] == '1') nm[i][j] = true;
cnt[i][j] = Integer.MAX_VALUE;
}
}
cnt[0][0] = 1;
BFS();
sb.append(cnt[n-1][m-1]);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void BFS() {
Deque<Obj> dq = new ArrayDeque<>();
// 현재 지점에 대한 객체(Deque에는 원시타입이 들어가지 않는다)
dq.offerFirst(new Obj(0, 0));
while(!dq.isEmpty()) {
Obj o = dq.pollLast();
int row = o.n;
int col = o.m;
if(row == n-1 && col == m-1) return;
// 이미 방문한 곳이면,
if(v[row][col]) continue;
v[row][col] = true;
// 상하좌우 따지기
// 상
if(row > 0) {
if(nm[row-1][col] && !v[row-1][col]) {
cnt[row-1][col] = Math.min(cnt[row][col] + 1, cnt[row-1][col]);
dq.offerFirst(new Obj(row-1, col));
}
}
//하
if(row < n-1) {
if(nm[row+1][col] && !v[row+1][col]) {
cnt[row+1][col] = Math.min(cnt[row][col] + 1, cnt[row+1][col]);
dq.offerFirst(new Obj(row+1, col));
}
}
//좌
if(col > 0) {
if(nm[row][col-1] && !v[row][col-1]) {
cnt[row][col-1] = Math.min(cnt[row][col] + 1, cnt[row][col-1]);
dq.offerFirst(new Obj(row, col-1));
}
}
//우
if(col < m-1) {
if(nm[row][col+1] && !v[row][col+1]) {
cnt[row][col+1] = Math.min(cnt[row][col] + 1, cnt[row][col+1]);
dq.offerFirst(new Obj(row, col+1));
}
}
}
}
public static class Obj{
int n;
int m;
public Obj(int n, int m) {
super();
this.n = n;
this.m = m;
}
}
}
풀이과정
- 처음에는 미로탐색이라고 해서 DFS로 풀었다.
- 그렇게 하다보니까 시간초과에 걸리고 말았다.
- 그렇다면 도달할 수 있는 최소의 칸수 이니까 BFS로 바꾸기로 하였다.
- 근데 DFS의 경우 재귀로 풀었는데 BFS의 경우 Queue를 써야 했는데, Queue에는 이차배열을 넣을 수가 없었다.
- 그래서 좌표를 어떻게 큐에 넣고 하나씩 꺼내올까를 생각하다가 객체를 하나 만들고 큐에 넣었다가 불러오기로 하였다.
- 객체를 만들었는데 객체(좌표)와 객체의 연결관계를 어떻게 처리해야 할까 고민하고 List에 넣어보려고 하고 여러가지 고민을 해보았지만 쉽게 풀리지 않았다.
- 다른 사람들의 문제를 참고하니, 객체와 객체의 연결, 즉 여기에서는 가는 길에 대한 배열을 따로 만들어서 좌표를 입력해 놓고
- 현재 객체의 위치에서 상하좌우를 따져 좌표배열을 참고하여 갈 수 있는지 따지고 객체를 큐에 넣고 하면 되었다.
- 아래는 DFS로 푼 풀이이다.
1
2
3
- 성공
- 메모리 : 14616 KB
- 시간 : 132 ms
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] nm;
static boolean[][] v;
static int[][] cnt;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
nm = new boolean[n][m];
v = new boolean[n][m];
cnt = new int[n][m];
for(int i = 0; i < n; i++) {
char[] tmp = br.readLine().toCharArray();
for(int j = 0; j < m; j++) {
if(tmp[j] == '1') nm[i][j] = true;
}
}
v[0][0] = true;
cnt[0][0] = 1;
DFS(0, 0);
sb.append(min);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void DFS(int i, int j) {
// 불필요한 계산 줄이기
if(min < cnt[i][j]) return;
// 맨아래 우측 도착
if(i == nm.length-1 && j == nm[0].length-1) min = (cnt[i][j] < min)? cnt[i][j] : min;
//상하좌우 따지기
//상
if(i != 0) {
if(nm[i-1][j] && !v[i-1][j]) {
//계산
cnt[i-1][j] = cnt[i][j] + 1;
v[i-1][j] = true;
DFS(i-1, j);
// 다른 루트를 위한 초기화
cnt[i-1][j] = 0;
v[i-1][j] = false;
}
}
//하
if(i != nm.length-1) {
if(nm[i+1][j] && !v[i+1][j]) {
cnt[i+1][j] = cnt[i][j] + 1;
v[i+1][j] = true;
DFS(i+1, j);
cnt[i+1][j] = 0;
v[i+1][j] = false;
}
}
//좌
if(j != 0) {
if(nm[i][j-1] && !v[i][j-1]) {
cnt[i][j-1] = cnt[i][j] + 1;
v[i][j-1] = true;
DFS(i, j-1);
cnt[i][j-1] = 0;
v[i][j-1] = false;
}
}
//우
if(j != nm[0].length-1) {
if(nm[i][j+1] && !v[i][j+1]) {
cnt[i][j+1] = cnt[i][j] + 1;
v[i][j+1] = true;
DFS(i, j+1);
cnt[i][j+1] = 0;
v[i][j+1] = false;
}
}
// 가다보니 마지막 지점 못 도달하고, 주변이 0인 경우
return;
}
}
보안점
- 노드가 단순한 숫자로 주어지고 노드와 노드의 연결이 주어진 DFS와 BFS 문제를 풀고 DFS와 BFS를 잘 풀 수 있을거라고 생각했는데
- 막상 좌표로 주어지고 객체를 활용해야 하고, 큐에 대해 몰랐던 부분들이 나오니 구현이 쉽지가 않았다.
- 객체 활용과 큐에 대해 하나 더 알게된 문제였다.