7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
bfs를 이용하여 익은 토마토와 근접해있는 토마토를 익게해서 모든 토마토를 익혀야합니다.
하지만 토마토가 들어있지 않은 칸이 있기때문에 모든 토마토가 익지 않을 수도 있습니다.
그리고 입력으로 이미 모든 토마토가 익어있으면 0을 출력해야합니다.
우선 입력을 받고, 0의 갯수(ans)를 모두 세어 유지합니다.
그리고 1을 입력받으면 덱에 넣고 방문처리도 해줍니다. (bfs 사용)
그 다음 bfs를 돌리기 전에 이미 ans가 0이면 0을 출력하고 리턴합니다.
확인이 끝나면 bfs를 돌려줍니다.
하루에 한칸씩 번지기때문에 덱에 있던 좌표들만 돌려야합니다. (t로 날짜 계산)
for문을 덱이 비어있지 않을동안 돌려주고 현재 덱의 크기를 size에 넣어서 size 만큼만 bfs를 돌려줍니다. (1일치)
이후에 ans가 0이 되면 모두 익었다는 뜻이므로 t를 출력합니다.
ans가 0이 되지 않았는데 덱이 비어버리면 모두 익지 않았다는 뜻이므로 -1을 출력합니다.
[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
|
#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int> > q;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[1001][1001];
int list[1001][1001];
int N, M, ans;
void bfs() {
int t = 1;
for (; !q.empty(); t++) {
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] == -1) continue;
q.push({ nx,ny });
visit[nx][ny] = true;
ans--;
}
}
if (!ans) {
cout << t << '\n';
return;
}
}
cout << "-1\n";
}
void func() {
if (!ans) {
cout << "0\n";
return;
}
bfs();
}
void input() {
cin >> M >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
if (!list[i][j])
ans++;
else if (list[i][j] == 1) {
q.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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Deque<int[]> dq = new ArrayDeque<>();
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static boolean visit[][];
static int list[][];
static int N, M, ans;
static void bfs() {
int t = 1;
for (; !dq.isEmpty(); t++) {
int size = dq.size();
while (size-- > 0) {
int x = dq.peekFirst()[0];
int y = dq.pollFirst()[1];
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 (list[nx][ny] == -1 || visit[nx][ny])
continue;
visit[nx][ny] = true;
dq.addLast(new int[] { nx, ny });
ans--;
}
}
if (ans == 0)
break;
}
if (ans == 0)
System.out.println(t);
else
System.out.println(-1);
}
static void func() {
if (ans == 0) {
System.out.println(0);
return;
}
bfs();
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
list = new int[N][M];
visit = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
if (list[i][j] == 0)
ans++;
else if (list[i][j] == 1) {
dq.addLast(new int[] { i, j });
visit[i][j] = true;
}
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 15653 구슬 탈출 4 (0) | 2021.02.22 |
|---|---|
| boj 1525 퍼즐 (0) | 2021.02.19 |
| boj 17135 캐슬 디펜스 (0) | 2021.02.17 |
| boj 16236 아기 상어 (0) | 2021.02.14 |
| boj 10026 적록색약 (0) | 2021.02.13 |