Last Update : 2022-06-22 00:26:07 +0900
토마토 (7576번)
https://www.acmicpc.net/problem/7576
풀이방법
- 숫자를 입력받을 때 익은 토마토의 좌표를
Queue에 넣는다. Queue에서 하나씩 빼면서 상하좌우에 현재값 +1 한다.- 방문하지 않은 곳은 -1로 설정한다.
- +1할때마다 최대값을 구한다.
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
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
int[][] dist = new int[N][M];
int zeroCount = 0;
Queue<int[]> queue = new LinkedList<>();
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
dist[i][j] = -1;
if (map[i][j] == 1) queue.add(new int[]{i, j});
if (map[i][j] == 0) zeroCount++;
}
}
int[] xPos = {1, 0, -1, 0};
int[] yPos = {0, 1, 0, -1};
int dx = 0; int dy = 0;
int max = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int i=0; i<4; i++) {
dx = cur[1] + xPos[i];
dy = cur[0] + yPos[i];
if (dx < 0 || dx >= M || dy < 0 || dy >= N) continue;
if (map[dy][dx] == 0 && dist[dy][dx] == -1) {
dist[dy][dx] = dist[cur[0]][cur[1]]+1;
max = Math.max(dist[dy][dx], max);
zeroCount--;
queue.add(new int[] { dy, dx });
}
}
}
if (zeroCount != 0) System.out.println(-1);
else if(max == 0) System.out.println(0);
else System.out.println(max+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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m, n;
int map[1002][1002];
int dist[1002][1002];
cin >> m >> n;
queue<pair<int, int>> Q;
int dayCount = 0;
int tomato_X = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> map[i][j];
if (map[i][j] == 0) tomato_X++;
else if (map[i][j] == 1) Q.push(pair(j, i));
dist[i][j] = -1;
}
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
while (!Q.empty()) {
pair<int, int> data = Q.front();
Q.pop();
for (int j=0; j<4; j++) {
int x = data.first + dx[j];
int y = data.second + dy[j];
// m*n 범위에서 벗어난 경우
if (x < 0 || y < 0 || x >= m || y >= n) continue;
// 토마토가 없는 경우
// 토마토가 이미 익은 경우
if (map[y][x] == 1 || map[y][x] == -1) continue;
dist[y][x] = dist[data.second][data.first]+1;
map[y][x] = 1;
Q.push(pair(x, y));
dayCount = max(dist[y][x], dayCount);
tomato_X--;
}
}
if (tomato_X != 0) {
cout << -1;
} else if (dayCount == 0) {
cout << 0;
} else {
cout << dayCount + 1;
}
return 0;
}
Comments powered by Disqus.