1. 문제
2636번: 치즈
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진
www.acmicpc.net
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
2. 풀이
Deque 사용
덱을 이용하면서 자연스럽게 정렬이 되려면 작은 값은 앞, 큰 값은 뒤에 추가하면 된다. 차이가 1밖에 나지 않기 때문에 가능한 방법이다.
공기라면 현재 시간 h와 동일한 값을 넣어서 deque의 맨 앞에 추가한다.
치즈라면 현재 시간 h에 1을 더해서 deque의 맨 뒤에 추가한다.
입력
치즈라면 true, 공기라면 false로 저장한다.
입력받은 치즈의 총 개수를 total에 저장한다.
정답으로 출력할 배열 answer은 0번째 자리에 시간, 1번째 자리에 한 시간 전 치즈의 개수를 저장한다.
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[][] board = new boolean[N][M];
boolean[][] visited = new boolean[N][M];
int total = 0;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<M;j++){
board[i][j] = st.nextToken().charAt(0)=='1';
if(board[i][j]) total++;
}
}
int[] answer = new int[]{0,total};//0:시간 1:개수(1시간전)
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
탐색 및 출력
1. 0,0자리는 항상 공기다. 따라서 덱에 0,0,0을 넣고, visited[0][0]에 방문처리한 뒤 반복탐색을 시작한다. [0]자리는 n, [1]자리는 m, [2]자리는 시간이다.
2. 만약 h가 answer[0]에 저장된 값보다 더 크다면 depth가 변경된 것이다. 따라서 answer[0]에는 h를 넣고 answer[1]에는 현재까지의 total값을 저장한다.
3. board[n][m]이 치즈라면 total값을 하나 뺀다.
4. 현재 자리에서 갈 수 있는 위치(nn,nm)로 사방탐색한다. 범위가 board에서 벗어나거나, 이미 방문한 적 있다면 제외한다.
5. board[nn][nm]이 치즈라면 deque의 끝에 추가한다. (nn,nm,h+1)
6. board[nn][nm]이 공기라면 deque의 앞에 추가한다. (nn,nm,h)
7. 방문처리한다.
8. 탐색이 전부 끝났다면 answer배열을 출력한다.
Deque<int[]> deque = new ArrayDeque<>();
deque.offer(new int[]{0,0,0});
visited[0][0] = true;
int n, m, h, nn, nm;
while(!deque.isEmpty()){
n = deque.peek()[0];
m = deque.peek()[1];
h = deque.poll()[2];
if(h>answer[0]) {
answer[0] = h;
answer[1] = total;
}
if(board[n][m]) total--;
for(int[] d:deltas){
nn = n+d[0];
nm = m+d[1];
if(nn<0 || nn>N || nm < 0 || nm > M || visited[nn][nm]) continue;
if(board[nn][nm]) deque.offerLast(new int[]{nn,nm,h+1});
else deque.offerFirst(new int[]{nn,nm,h});
visited[nn][nm] = true;
}
}
System.out.println(answer[0]+"\n"+answer[1]);
전체 코드
import java.io.*;
import java.util.*;
public class BOJ_2636_치즈 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[][] board = new boolean[N][M];
boolean[][] visited = new boolean[N][M];
int total = 0;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<M;j++){
board[i][j] = st.nextToken().charAt(0)=='1';
if(board[i][j]) total++;
}
}
int[] answer = new int[]{0,total};//0:시간 1:개수(1시간전)
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
Deque<int[]> deque = new ArrayDeque<>();
deque.offer(new int[]{0,0,0});
visited[0][0] = true;
int n, m, h, nn, nm;
while(!deque.isEmpty()){
n = deque.peek()[0];
m = deque.peek()[1];
h = deque.poll()[2];
if(h>answer[0]) {
answer[0] = h;
answer[1] = total;
}
if(board[n][m]) total--;
for(int[] d:deltas){
nn = n+d[0];
nm = m+d[1];
if(nn<0 || nn>N || nm < 0 || nm > M || visited[nn][nm]) continue;
if(board[nn][nm]) deque.offerLast(new int[]{nn,nm,h+1});
else deque.offerFirst(new int[]{nn,nm,h});
visited[nn][nm] = true;
}
}
System.out.println(answer[0]+"\n"+answer[1]);
}
}
PriorityQueue 사용
위의 deque을 priorityqueue로 바꾼 버전이다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[][] board = new boolean[N][M];
boolean[][] visited = new boolean[N][M];
int total = 0;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<M;j++){
board[i][j] = st.nextToken().charAt(0)=='1';
if(board[i][j]) total++;
}
}
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
pq.offer(new int[]{0,0,0});
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
int n, m, h;
int nn, nm;
int[] answer = new int[]{0,total};
visited[0][0] = true;
while(!pq.isEmpty()){
n = pq.peek()[0];
m = pq.peek()[1];
h = pq.poll()[2];
if(h>answer[0]) {
answer[0] = h;
answer[1] = total;
}
if(board[n][m]) total--;
for(int[] d:deltas){
nn = n+d[0];
nm = m+d[1];
if(nn<0 || nn>=N || nm < 0 || nm >= M || visited[nn][nm]) continue;
if(board[nn][nm]) pq.offer(new int[]{nn,nm,h+1});
else pq.offer(new int[]{nn,nm,h});
visited[nn][nm] = true;
}
}
System.out.println(answer[0]+"\n"+answer[1]);
}
}
BFS 사용
위의 두 풀이보다 조금 더 복잡하다. 치즈가 녹아서 공기가 된 것과 이미 공기였던 것에 차이를 둬야하기 때문이다.
순서는 입력-> {공기체크-치즈녹이기}+ -> 새로 녹인 치즈가 없다면 한 시간 전 치즈 개수와 시각을 출력한다.
치즈 저장 배열과 공기 저장 배열을 따로 두는 이유는 치즈 속에 숨어있는 공기 때문이다.
| int R,C | 전체 크기 |
| int count | 한 시간 전 치즈 개수 |
| boolean[][] cheese | 치즈저장 배열 |
| boolean[][] air | 공기저장 배열 |
Main
1. R,C,cheese에 입력받은 값을 저장한다.
2. hour초기값을 0으로 두고 하나라도 녹인 치즈가 있다면(removeCheese=true) 시간을 추가한다.
3. 반환값이 false라면 반복을 중단하고 hour과 count(한 시간 전 치즈 개수)를 출력한다.
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
cheese = new boolean[R][C];
air = new boolean[R][C];
for (int i = 0; i < R; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < C; j++) {
cheese[i][j] = st.nextToken().equals("1");
}
}
int hour = 0;
while (removeCheese()) {
hour++;
}
System.out.println(hour);
System.out.println(count);
}
치즈 녹이기
1. 치즈를 녹이기 전 먼저 공기부터 체크하는 메서드를 부른다.
2. board를 처음부터 끝까지 탐색하면서 아직 녹지 않은 치즈고 먹을 수 있다면(canMelt메서드) 치즈를 녹이고 cnt++한다.
3. 만약 녹인 치즈 개수가 0이 아니라면 count에 cnt를 저장하고 true를 반환한다.
4. 녹인 치즈 개수가 0개라면 false를 반환해서 메인의 반복을 멈추도록 한다.
private static boolean removeCheese() {
checkAir();
int cnt = 0;
for (int i = 1; i < R - 1; i++) {
for (int j = 1; j < C - 1; j++) {
if (cheese[i][j] && canMelt(i, j)) {
cheese[i][j] = false;
cnt++;
}
}
}
if (cnt != 0) {
count = cnt;
return true;
}
return false;
}
공기체크
현재 판에 공기가 어디있는지 체크한다.
0,0은 항상 공기이므로 큐에 {0,0}위치를 넣고 탐색한다.
private static void checkAir() {
boolean[][] visited = new boolean[R][C];
visited[0][0] = true;
air[0][0] = true;
int[] pos = {0, 0};
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(pos);
while (!queue.isEmpty()) {
pos = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = pos[0] + deltas[d][0];
int nc = pos[1] + deltas[d][1];
if (isValid(nr, nc) && !cheese[nr][nc] && !visited[nr][nc]) {
visited[nr][nc] = true;
air[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
}
범위체크
static private boolean isValid(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}
녹일 수 있는지 체크
현재 위치 r,c에 있는 치즈가 위아래양옆으로 공기와 닿아있다면 바로 true, 아니라면 false를 반환한다.
static private boolean canMelt(int r, int c) {
for (int d = 0; d < 4; d++) {
int nr = r + deltas[d][0];
int nc = c + deltas[d][1];
if (isValid(nr, nc) && air[nr][nc]) return true;
}
return false;
}
전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int count, R, C;
static boolean[][] cheese,air;
static int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
cheese = new boolean[R][C];
air = new boolean[R][C];
for (int i = 0; i < R; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < C; j++) {
cheese[i][j] = st.nextToken().equals("1");
}
}
int hour = 0;
while (removeCheese()) {
hour++;
}
System.out.println(hour);
System.out.println(count);
}
private static void checkAir() {
boolean[][] visited = new boolean[R][C];
visited[0][0] = true;
air[0][0] = true;
int[] pos = {0, 0};
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(pos);
while (!queue.isEmpty()) {
pos = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = pos[0] + deltas[d][0];
int nc = pos[1] + deltas[d][1];
if (isValid(nr, nc) && !cheese[nr][nc] && !visited[nr][nc]) {
visited[nr][nc] = true;
air[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
}
private static boolean removeCheese() {
checkAir();
int cnt = 0;
for (int i = 1; i < R - 1; i++) {
for (int j = 1; j < C - 1; j++) {
if (cheese[i][j] && canMelt(i, j)) {
cheese[i][j] = false;
cnt++;
}
}
}
if (cnt != 0) {
count = cnt;
return true;
}
return false;
}
static private boolean isValid(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}
static private boolean canMelt(int r, int c) {
for (int d = 0; d < 4; d++) {
int nr = r + deltas[d][0];
int nc = c + deltas[d][1];
if (isValid(nr, nc) && air[nr][nc]) return true;
}
return false;
}
}3. 결과
노란색이 deque사용
파란색이 priorityqueue사용
분홍색이 bfs 사용한 결과다.
priorityqueue는 내부 정렬 시간이 있어서 가장 오래걸리고, bfs는 메서드 호출하고 공기체크할 때 매번 처음부터 bfs탐색하기 때문에 시간이 더 걸린 것 같다.
이 문제의 가장 좋은 풀이는 deque을 이용한 풀이라고 생각한다.
'코딩테스트 > BOJ' 카테고리의 다른 글
| [BOJ] 9465 스티커 - JAVA (0) | 2023.05.19 |
|---|---|
| [BOJ] 11657 타임머신 - JAVA (0) | 2023.05.18 |
| [BOJ] 20304 비밀번호 제작 - JAVA (0) | 2023.05.16 |
| [BOJ] 1958 LCS 3 - JAVA (2) | 2023.05.08 |
| [BOJ] 9252 LCS 2 - JAVA (0) | 2023.05.07 |
댓글