2178번 미로 탐색
2020. 2. 4. 15:11ㆍLearn/Algorithm
|
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
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int test;
static int N;
static int M;
static int sum;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int arr[][] = new int[N+1][M+1];
boolean boo[][] = new boolean [N+1][M+1];
String s;
for(int i = 1; i <= N; i++) {
s = sc.next();
for(int j = 1; j <= M; j++) {
arr[i][j] = s.charAt(j-1)- '0';
}
}
sum = 0;
BFS(1,1,arr,boo);
System.out.println(sum);
}
public static void BFS(int n , int w,int ar[][], boolean bo[][]) {
Queue<Integer> qu = new LinkedList<>();
Queue<Integer> qu2 = new LinkedList<>();
Queue<Integer> qu3 = new LinkedList<>();
Queue<Integer> qu4 = new LinkedList<>();
qu.add(n);
qu2.add(w);
int cnt = 1;
bo[n][w] = true;
while(!qu.isEmpty()) {
while(!qu.isEmpty()) {
for(int i = 0; i <4; i++) {
int nn = qu.peek() + dx[i];//불리언컨틴뉴만들기
int ww = qu2.peek() + dy[i];
if(nn > 0 && nn < N+1 && ww > 0 && ww < M+1 ) {
if(bo[nn][ww] == true)
continue;
if(ar[nn][ww] == 1) {
bo[nn][ww] = true;
qu3.add(nn);
qu4.add(ww);
}
}
}
if(qu.peek() == N && qu2.peek() == M)
sum = cnt;
qu.poll();
qu2.poll();
if(qu.isEmpty())
cnt++;
}
while(!qu3.isEmpty()) {
for(int i = 0; i <4; i++) {
int nn = qu3.peek() + dx[i];//불리언컨틴뉴만들기
int ww = qu4.peek() + dy[i];
if(nn > 0 && nn < N+1 && ww > 0 && ww < M+1 ) {
if(bo[nn][ww] == true)
continue;
if(ar[nn][ww] == 1) {
bo[nn][ww] = true;
qu.add(nn);
qu2.add(ww);
}
}
}
if(qu3.peek() == N && qu4.peek() == M)
sum = cnt;
qu3.poll();
qu4.poll();
if(qu3.isEmpty())
cnt++;
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
|
BFS의 depth를 세어주면 되는 문제.
pair를 사용한다면 queue의 갯수를 줄일 수 있을 것 같았으나
아쉽게도 자바에는 queue가 없으므로 class pair로 하나 만들어서 수행해도 되었으나
극도의 귀차니즘으로 queue를 4개나 만들어버렸다....
예외처리로
시작할 때의 지나는 길 갯수가 1인 점과
모든 탐색 depth가 아닌마지막 N과 M좌표에 도달할때를
출력한다면 올바른 정답을 도출할 수 있을것이다.
'Learn > Algorithm' 카테고리의 다른 글
| 1225 암호생성기 (0) | 2020.02.05 |
|---|---|
| 7576 토마토 (0) | 2020.02.04 |
| 1012 유기농 배추 (0) | 2020.02.04 |
| 2667 단지번호붙이기 (0) | 2020.02.04 |
| 1260 DFS 와 BFS - 백준 (0) | 2020.02.04 |