백준 7576번 : 토마토
이번 문제는 격자 모양 상자에 토마토가 담겨있고 각 토마토는 -1, 0, 1로 표현한다.
-1 = 토마토가 들어있지 않은 칸
0 = 익지 않은 토마토
1 = 익은 토마토
로 표현하며, 상하좌우로 인접한 토마토끼리 영향을 받는다.
즉, 1과 인접한 0은 영향을 받아 하루가 지나면 1이 된다.
단, 대각선으로는 영향이 미치지 않는다.
지금 껏 풀었던 문제들과 마찬가지로 상하좌우 좌표 값을 설정하고 상자의 상태 값을 표현할 arr 배열, 가로, 세로 길이를 멤버 변수로 선언했다.
1
2
3
4
5
6
7
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] arr;
static int n, m;
...
}
다음으로는 가로, 세로, 그래프를 가공하여 그래프를 표현했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
arr = new int[n][m];
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1) {
q.offer(new int[]{i, j});
}
}
}
배열을 활용하여 그래프를 구현하고, Q를 미리 초기화해서 시작 위치를 잡아준다.
이는 시작 위치가 일정하지 않고 반복되기 때문에 바로 BFS 탐색을 시작할 수 있도록 그래프 생성과 동시에 시작 위치를 파악하는 것이다.
쉽게 말해 그래프가 생성되면서 1이 삽입되면 해당 부분부터 탐색을 시작한다고 지정하는 것이다.
이렇게 구현하면 arr 자체가 방문 여부를 체크하는 역할을 수행하기 때문에 별도의 boolean 타입 배열을 사용하지 않는다.
이로써 큐에는 bfs 탐색할 시작 지점들을 미리 저장해 두었기 때문에 메모리 사용량도 줄일 수 있다.
다음으로는 즉시 BFS 탐색을 시작한다.
BFS 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void bfs(Queue<int[]> q) {
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 0) {
q.offer(new int[]{nx, ny});
arr[nx][ny] = arr[cur[0]][cur[1]] + 1;
}
}
}
}
}
이번 탐색은 이전에 활용했던 BFS 탐색과 차이가 있다.
앞서 말했듯이 별도의 boolean 타입 배열을 사용하지 않는다.
또한, arr 자체가 방문 여부를 고려하는 역할을 하기 때문에 arr 생성할 때 삽입된 시작 지점부터 bfs를 반복하면 된다.
상세한 로직은 좌표 탐색 BFS와 같지만 아직 익지 않은 토마토, 즉, 좌표가 0인 경우 마다 arr 배열의 해당 좌표 값을 이전 좌표 + 1로 표현한다.
쉽게 말해 arr은 두고 시작 지점을 미리 파악한 bfs를 활용하여 arr의 상태를 변경하는 방식이다.
위 과정을 거치면, arr에는 익은 토마토 총계와 빈 구역 두 개로 끝나게 된다.
1
2
3
4
5
6
7
8
9
10
11
12
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println("-1");
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
마지막으로 배열을 순회하여 토마토가 하나라도 익지 않았다면 -1을 리턴하고 그게 아니라면 배열 내부의 가장 큰 값에서 1을 빼면 된다.
다시 말해, 시작한 날을 빼준 배열 요소 중 최대값이 토마토가 전부 읽을 때 까지 걸리는 총 일수이다.
아래는 전체 소스코드이다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] arr;
static int n,m;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
arr = new int[n][m];
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1) {
q.offer(new int[]{i, j});
}
}
}
bfs(q);
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println("-1");
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
}
public static void bfs(Queue<int[]> q) {
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 0) {
q.offer(new int[]{nx, ny});
arr[nx][ny] = arr[cur[0]][cur[1]] + 1;
}
}
}
}
}
}
이 문제는 이전에 풀었던 것과 조금 결이 다르기도하고 애초에 0, -1, 1 각각 어떻게 순회해야할지 엄청 고민이 되었었다.
결과적으로는 배열과 큐를 동시에 사용해서 풀어냈지만 비슷한 문제만 풀다보니 머리가 좀 굳어 있었던 것 같다.
어찌되었던 이번 문제를 통해 조금 어려운 BFS 탐색 문제를 접해볼 수 있었고, 아직까진 응용이 어려운 느낌이다.