https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
두 종류의 bfs을 사용하여 해결하였습니다.
하나는 물에 대한 bfs,
하나는 고슴고치에 대한 bfs입니다.
[물이 흐르는 조건]
1. 돌을 통과할 수 없다.
2. 비버의 소굴로 이동할 수 없다.
[고슴도치가 이동하는 조건]
1. 돌을 통과할 수 없다.
2. 물로 차있는 구역으로 이동할 수 없다.
3. 물이 찰 예정인 칸으로 이동할 수 없다.
물이 찰 예정인 칸으로 이동할 수 없다는 말은 물과 고슴도치가 같은 시간에 같은 장소에 갈 수 없다는 것입니다.
따라서 물에 대한 bfs로 물이 먼저 흐르게 하고, 그 다음에 고슴도치에 대한 bfs로 고슴도치를 이동시키면 되는 문제입니다.
이 과정을 무한반복하여 고슴도치가 비버의 소굴로 이동하면 그 시간을 출력하고,
과정을 반복하던 도중에 고슴도치의 좌표가 들어있는 큐가 비어있으면 탈출에 실패했다는 것이니, "KAKTUS"를 출력합니다.
C++ 소스 추가하였습니다.
[C++]
|
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
|
#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int> > q;
queue<pair<int, int> > wq;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[51][51], wvisit[51][51], chk;
char list[51][51];
int N, M, ex, ey;
void waterbfs() {
int qsize = wq.size();
while (qsize--) {
int x = wq.front().first;
int y = wq.front().second;
wq.pop();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (wvisit[nx][ny] || list[nx][ny] == 'D' || list[nx][ny] == 'X') continue;
wq.push({ nx,ny });
wvisit[nx][ny] = true;
list[nx][ny] = '*';
}
}
}
void bfs() {
int qsize = q.size();
while (qsize--) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (visit[nx][ny] || list[nx][ny] == 'X' || list[nx][ny] == '*') continue;
if (list[nx][ny] == 'D') {
chk = true;
return;
}
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
}
void func() {
for (int T = 1; ; T++) {
waterbfs();
bfs();
if (chk) {
cout << T << '\n';
return;
}
else if (q.empty()) {
cout << "KAKTUS\n";
return;
}
}
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
if (list[i][j] == 'S') {
q.push({ i,j });
visit[i][j] = true;
}
else if (list[i][j] == 'D') {
ex = i;
ey = j;
}
else if (list[i][j] == '*') {
wq.push({ i,j });
visit[i][j] = true;
}
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
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.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static char list[][] = new char[50][50];
static boolean qvisit[][] = new boolean[50][50];
static boolean wvisit[][] = new boolean[50][50];
static int N, M, ex, ey;
static Queue<int[]> q = new LinkedList<>();
static Queue<int[]> w = new LinkedList<>();
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static void waterbfs() {
int size = w.size();
while (size-- > 0) {
int x=w.peek()[0];
int y=w.peek()[1];
w.remove();
for(int i=0; i<4; i++) {
int nx=x+direct[i][0];
int ny=y+direct[i][1];
if(nx<0 || ny<0 || nx>=N || ny>=M)
continue;
if(wvisit[nx][ny] || list[nx][ny]=='X' || list[nx][ny]=='D')
continue;
w.add(new int[] {nx,ny});
wvisit[nx][ny]=true;
}
}
}
static boolean bfs() {
int size=q.size();
while(size-->0) {
int x=q.peek()[0];
int y=q.peek()[1];
q.remove();
for(int i=0; i<4; i++) {
int nx=x+direct[i][0];
int ny=y+direct[i][1];
if(nx<0 || ny<0 || nx>=N || ny>=M)
continue;
if(qvisit[nx][ny] || wvisit[nx][ny] || list[nx][ny]=='X')
continue;
if(nx==ex && ny==ey)
return true;
q.add(new int[] {nx,ny});
qvisit[nx][ny]=true;
}
}
return false;
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
for (int j = 0; j < M; j++) {
char ch = list[i][j];
if (ch == 'S') {
q.add(new int[] { i, j });
qvisit[i][j] = true;
} else if (ch == '*') {
w.add(new int[] { i, j });
wvisit[i][j] = true;
} else if (ch == 'D') {
ex = i;
ey = j;
}
}
}
}
public static void main(String[] args) throws Exception {
input();
for(int T=1; ; T++) {
waterbfs();
if(bfs()) {
System.out.println(T);
break;
}
if(q.isEmpty()) {
System.out.println("KAKTUS");
break;
}
}
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17142 연구소 3 (0) | 2021.01.22 |
|---|---|
| boj 2636 치즈 (0) | 2021.01.22 |
| boj 1039 교환 (0) | 2021.01.22 |
| boj 2234 성곽 (0) | 2021.01.22 |
| boj 17472 다리 만들기 2 (0) | 2021.01.22 |