백준 2636. 치즈
31 Mar 2021문제 바로가기
문제 요약
치즈가 공기중에 닿으면 닿은 부분이 모두 녹고 치즈 사이의 공간에는 공기가 없어 녹지 않는다. 1초마다 공기와 닿고있는 면적이 모두 녹는데, 그렇다면 치즈가 모두 녹아 없어지는데 걸리는 시간과, 모두 녹기 한시간 전에 남아있는 치즈가 놓여있는 칸의 개수를 구하는 프로그램을 작성하시오.
문제 풀이 포인트
BFS를 사용하되 조금 관점을 비틀어서 생각해봐야할 문제였다. 대부분 N*M의 map에서 0이 아닌 숫자로 표시되어있는 점을 찾아 BFS를 찾지만 이문제는 치즈 바깥의 0을 찾아 찾은 0들과 붙어있는 1을 모두 체크하여 없애는 방식으로 접근해야해서 BFS를 여러번 사용해야하는 문제로 BFS만 잘 구현할 수 있다면 어렵지 않은 문제다.
아래 첨부한 코드는 조금 긴데, 그렇게 print 메소드나 같은 기능을 하는 여러 메소드들을 적어두어 길어졌으니 한번 보면서 어떤 것을 사용하는 좋은지 생각해보길 바란다.
내가 푼 코드에서는
- 치즈가 map에 남아있는지 체크하는 findLR() 메소드
- 치즈의 바깥쪽을 색칠하는 colorBFS() 메소드
- 닿아있는 치즈를 녹이는 melt() 메소드
- 색칠한 바깥쪽을 다시 원상태로 되돌리는 colorBFS() 메소드 총 4가지의 과정으로 문제를 해결했다.
- findLR() 메소드에서는 치즈를 덮을 수 있는 최대 크기의 사각형을 만들어 해당 공간만 BFS를 돌리게 작성을 하였는데 전체 공간을 BFS로 돌리는 것과 시간이 큰 차이가 없었다.
- 색칠을 하고 되돌리는 코드가 동일한 형태를 띄어 바꾸고 싶은 상태값을 인자로 넘겨 색칠하는 메소드로 작성했다. 근데 그냥 색칠된 부분들을 다 Stack에 담아서 색을 되돌리는 것이 속도가 더 빠르다.
문제 코드[JAVA]
코드 펼치기
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map;
static int lx, ly, rx, ry;
static int ansCnt, ansTime;
static class Point {
int x, y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
// 사각형을 만들기 위한 x, y 좌표 설정
lx = Integer.MAX_VALUE;
ly = Integer.MAX_VALUE;
rx = 0;
ry = 0;
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());
}
}
function();
System.out.println(ansTime);
System.out.println(ansCnt);
}
private static void function() {
ansCnt = 0;
ansTime = 0;
while(findLR()) {
Point start = new Point(lx -1, ly -1);
colorBFS(start, 2);
ansCnt = melt();
colorBFS(start, 0);
//delete();
ansTime++;
}
}
// 2로 색칠한 스택에 담겨있는 좌표들을 되돌리는 메소드
private static void delete() {
while(!stack.isEmpty()) {
Point cur = stack.pop();
map[cur.x][cur.y] = 0;
}
}
// 치즈를 녹이는 메소드, 2와 맞닿아있으면 다 녹인다.
private static int melt() {
int cnt = 0;
for(int i = lx-1; i <= rx +1; i++) {
for(int j = ly -1; j <= ry+1; j++) {
if(map[i][j] == 1) {
for(int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if(map[nx][ny] == 2) {
cnt++;
map[i][j] = 0;
break;
}
}
}
}
}
//print();
return cnt;
}
// 치즈를 사각형으로 덮을 수 있는 가장 작은 사각형 구하기
private static boolean findLR() {
boolean flag = false;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1) {
flag = true;
lx = Math.min(i, lx);
ly = Math.min(j, ly);
rx = Math.max(i, rx);
ry = Math.max(j, ry);
}
}
}
return flag;
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static Stack<Point> stack = new Stack<>();
// 색칠하기 BFS
private static void colorBFS(Point start, int color) {
Queue<Point> queue = new LinkedList<>();
boolean[][] v= new boolean[N][M];
queue.add(start);
v[start.x][start.y] = true;
map[start.x][start.y]= color;
stack.add(start);
// 1을 둘러싸고 있는 벽면을 다 칠함
while(!queue.isEmpty()) {
Point cur = queue.poll();
for(int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if(safy(nx, ny) && !v[nx][ny] && map[nx][ny] == Math.abs(2 - color)) {
map[nx][ny] = color;
queue.offer(new Point(nx,ny));
stack.add(new Point(nx, ny));
}
}
}
//print();
}
private static void print() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
private static boolean safy(int nx, int ny) {
if(nx >= lx-1 && nx <= rx+1 && ny >= ly -1 && ny <= ry+1) return true;
else return false;
}
}