[PS] 백준 2638 - 치즈

 

* 문제링크

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

 

* 유사문제

BOJ 2573 - 빙산

https://www.acmicpc.net/problem/2573

 

2573번: 빙산

* 풀이 접근

 

1. 기존에 풀었던 빙산과 유사하다. -> 빙산처럼 풀어볼까?

2. 치즈와 치즈 사이에 있는 공기처리를 어떻게 할 것인지?

3. 공기와 두면 이상 접촉한 치즈 제거 

 

* 풀이 중 해맨 포인트 

 

1. 처음엔 치즈가 주위의 상, 하, 좌, 우 4방향 중 두 군데 이상 공기와 접촉해있으면 즉시 제거하였으나 이렇게 진행하게 되면 주변 치즈에 영향을 줄 수 있어 변경하였다.

치즈는 1, 공기는 0 이 아니라 치즈는 1, 공기는 -1, 내부 공기는 0 과 같이 3개의 포인트로 나누어 접근하였다.

(치즈를 즉시 제거 하여 공기로 바꾼다면 주변 치즈에 영향을 줄 수 있음)

 

2. 위의 1번 사항을 고려하고 작성하였음에도 TC의 답보다 나의 답이 1 크게 나왔다. 그래서 그냥 끼워맞추기 식으로 -1 한채로 제출해보니 정답처리가 됐다.

 

이유는 치즈가 하나도 없으면 0시간이 걸려야하는데 나는 while문에 들어갈 때 바로 시간을 +1 해주어서 그런 것이었다. 소 뒷걸음질 치다가 쥐잡은 격.. 

 

* 풀이 후 소감

 

백준 사이트의 2573번 문제 빙산과 유사하다는 생각에 빙산처럼 푸는 기억을 떠올린 것이 너무 아쉽다.

문제의 개념을 파악한 것이 아니라 문제를 양치기로 많이 푼 뒤 비슷한 유형을 기억속에서 억지로 끄집어낸 느낌?

나중에 시간될 때 bfs로도 한번 풀어보아야겠다.

다음부터는 조금 더 꼼꼼하게 접근해야겠다.

 

-----------------------------------------------------------------------------------------------------------------------------

 

* 나의 코드 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baek_2638_Gold4_치즈 {

	static int N;
	static int M;
	static int[][] map;
	static int ans;
	static int[][] dirs = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static boolean[][] visited;
	private static boolean isSafe(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}



	private static void dfs(int x, int y) {
		map[x][y] = -1;
		visited[x][y] = true;
		for(int k = 0 ; k < dirs.length ; k++) {
			int nx = x + dirs[k][0];
			int ny = y + dirs[k][1];
			if(isSafe(nx,ny) && map[nx][ny] != 1 && !visited[nx][ny]) {
				dfs(nx,ny);
			}
		}
	}

	private static boolean deleteCheese(int x, int y) {
		int cnt = 0;
		for(int k = 0 ; k < dirs.length ; k++) {
			int nx = x + dirs[k][0];
			int ny = y + dirs[k][1];
			if(isSafe(nx,ny) && map[nx][ny] == -1) {
				cnt++;
			}
		}
		if(cnt >= 2) {
			map[x][y] = 0;
			return true;
		}
		return false;
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		ans = 0;
		
		while(true) {
			ans++;
			visited = new boolean[N][M];
			
			boolean flag = false;
			dfs(0,0);
			for(int i = 0 ; i < N ; i++) {
				for(int j = 0 ; j < M; j++) {
					if(map[i][j] == 1 && deleteCheese(i,j)) {
						flag = true;
					}
				}
			}
			if(!flag) {
				System.out.println(ans-1);  //치즈가 하나도 없으면 0시간이 걸려야하는데 시작할 때 ans++을 해주니까 -1 해줘야됨 아니면 ans = -1 해도 됨
				break;
			}
		}

	}

}