2636 문제 링크
https://www.acmicpc.net/problem/2636
문제 설명
입출력
코드
|
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
|
import java.util.*;
import java.io.*;
public class Main {
private static int r, c;
private static int total = 0;
private static String[] input;
private static int[][] arr;
private static int[] dx = {0, 1, 0, -1};
private static int[] dy = {1, 0, -1, 0};
private static int time = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input = br.readLine().split(" ");
r = Integer.parseInt(input[0]);
c = Integer.parseInt(input[1]);
arr = new int[r][c];
for (int i = 0; i < r; i++) {
input = br.readLine().split(" ");
for (int j = 0; j < c; j++) {
arr[i][j] = Integer.parseInt(input[j]);
if (arr[i][j] == 1) total++;
}
}
int lastCheese = 0;
while(total > 0) {
lastCheese = total; markOutside();
melt();
time++;
}
bw.write(String.valueOf(time));
bw.newLine();
bw.write(String.valueOf(lastCheese));
bw.flush();
}
private static void markOutside() {
Queue<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (arr[i][j] == -1) arr[i][j] = 0;
}
}
arr[0][0] = -1; // -1이면 outside
queue.offer(new int[] {0, 0});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (arr[nx][ny] == -1 || arr[nx][ny] == 1) continue;
arr[nx][ny] = -1;
queue.offer(new int[] {nx, ny});
}
}
}
private static void melt() {
List<int[]> list = new ArrayList<>();
for (int i = 1; i < r - 1; i++) {
for (int j = 1; j < c - 1; j++) {
if (arr[i][j] != 1) continue;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (arr[nx][ny] == -1) {
list.add(new int[] {i, j});
break;
}
}
}
}
for (int[] pos : list) {
arr[pos[0]][pos[1]] = 0;
total--;
}
}
}
|
cs |
|
|
|
알고리즘 설명
요새 코딩테스트는 거의 구현 문제만 푸는 거 같네요. 신기한 건, 비슷한 유형이라도 문제를 풀 때마다 새롭게 느껴진다는 점입니다.
해당 문제는 구현 + BFS 문제로 치즈 문제가 두 개가 있는데, 2638번도 해당 문제랑 거의 유사하니 푸는김에 풀어보시는 것도 좋을 것 같습니다.
이 문제의 핵심은 공기와 닿은 치즈만 녹는다는 점입니다. 판의 가장자리에는 치즈가 놓일 수 없다고 조건이 걸려있기 때문에 (0, 0)을 시작점으로 해서 BFS 탐색을 하는 것입니다.
문제에서 구해야 하는 것은
1️⃣ 모든 치즈가 녹는 데 걸린 시간,
2️⃣ 치즈가 모두 녹기 한 시간 전의 치즈 개수입니다.
이를 구하기 위해 아래의 네 단계를 반복합니다.
- 외부 공기 표시
- 존재하는 치즈의 양 세기
- 치즈 녹이기
- 시간 증가
모든 치즈가 녹아 없어질 때까지 위 과정을 반복하면, 최종적으로 time (걸린 시간) 과 lastCheese (마지막 한 시간 전에 남은 치즈 수)를 구할 수 있습니다.
코드 해석
arr 배열에 주어진 치즈 판을 입력하고, 값이 1이면 치즈, 0이면 공기를 의미합니다. 입력을 받으면서 치즈의 총 개수를 total 변수에 저장해둡니다.
치즈의 총 개수를 나타내는 total이 0보다 클 때, 즉 치즈가 모두 녹을 때까지 시뮬레이션을 수행합니다. 매 반복마다 현재 존재하는 치즈의 갯수인 total을 lastCheese에도 넣어주고, markOutside() 함수를 통해 외부 공기를 표시하고, 그 다음 melt() 함수를 이용해 치즈를 녹입니다. 그리고 해당 두 함수를 전부 거칠 때마다 time 변수를 1 증가 시킵니다.
markOutside() 함수는 BFS를 이용해 외부 공기를 구분합니다. 문제 조건상 판의 가장자리는 항상 공기이므로 (0, 0)부터 시작해 상하좌우 방향으로 BFS 탐색하면서 공기 영역을 -1로 표시합니다.
이후 melt() 함수로 외부 공기(-1)와 맞닿아있는 치즈(1)부분을 찾아 배열 전체를 순회하면서 각 치즈 부분의 상하좌우 중 하나라도 외부공기(-1)와 맞닿아 있다면 현재 치즈의 좌표를 list에 넣고 해당 치즈 좌표의 탐색을 종료합니다. 탐색이 끝난 후 리스트에 저장된 모든 좌표의 치즈를 녹여 0으로 바꾸고, total 값을 갱신합니다.
탐색이 끝난 후 한꺼번에 녹이는 이유는, 탐색 도중에 값을 바로 변경하면 같은 시간대에 녹지 않아야 할 치즈가 잘못 녹는 오류가 발생할 수 있기 때문입니다.
이후, total > 0을 만족하지 않아 while문을 빠져나오게 되면 total과 lastCheese값을 출력합니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1761 정점들의 거리 - JAVA (0) | 2025.11.22 |
|---|---|
| 백준 1443 망가진 계산기 - JAVA (0) | 2025.11.10 |
| 백준 1019 책 페이지 - JAVA (0) | 2025.10.20 |
| 백준 1941 소문난 칠공주 - JAVA (0) | 2025.10.16 |
| 백준 2573 빙산 - JAVA (0) | 2025.09.10 |