[Gold3-JAVA] 백준 2638 - 치즈

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

2638번: 치즈

 

 

🤔문제 풀이

상당히 난이도가 있었던 그래프 탐색 문제였다.

전체적인 로직은 어렵지 않았지만 외부공기와 내부공기를 파악해 치즈가 내부에 있는지

외부에 있는지를 판단하는 것이 어려웠다.

 

본인은 다음과 같은 로직 순서로 풀이를 진행했다.

 

1. map에 치즈 정보를 받는다.

2. 가장 자리에는 치즈가 놓이지 않기 때문에 0,0 좌표부터 DFS 탐색을 진행하며 외부 공기 위치를 파악했다.

3. 삭제할 치즈를 파악하고 삭제한다.

4. map에서 치즈가 남아있는지를 확인하고 남아있다면 1부터 다시 수행한다.

 

// dfs 탐색으로 외부 공기의 위치 파악 메서드
	public static void checkOutSideAir(int x, int y) {
		visit[x][y] = true;
		map[x][y] = 2;
		
		for(int i = 0; i<4; i++) {
			int nextX = x+dx[i];
			int nextY = y+dy[i];
			
			if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;
			if(map[nextX][nextY] == 1 || visit[nextX][nextY])
				continue;
			
			checkOutSideAir(nextX, nextY);
		}
	}

 

외부 공기의 위치를 판단하는 메서드에서 탐색이 가능한 모든 좌표의 값을 2로 바꾸는 것으로

외부 공기임을 표현했다. 치즈 안의 내부공기는 그래프 탐색으로 도달할 수 없으니 0으로 남을 것이다.

 

// 삭제될 치즈인지 확인하는 메서드
	public static boolean isDeleteCheese(int x, int y) {
		int count = 0;
		for(int i = 0; i<4; i++) {
			int nextX = x+dx[i];
			int nextY = y+dy[i];
			if(map[nextX][nextY] == 2)
				count++;
		}
		
		if(count >= 2)
			return true;
		else
			return false;
	}

 

삭제될 치즈인지 확인하는 메서드에서는 치즈 좌표의 상하좌우를 확인하여 만약 값이 2인 경우

count를 증가하여 count의 값이 2이상인 경우 삭제할 치즈로 판단하여 Queue에 담아놓았가 파악이 끝난 후 

일괄 삭제하도록 했다.

내부 공기의 좌표 값은 0이기 때문에 내부에 있는 치즈는 count가 2가 안되므로 이번 차수에 삭제되지 않는다.

 

🚨CODE

import java.io.*;
import java.util.*;

public class Main {
	static int n,m;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	public static void main(String[] args) throws Exception {
		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];
		visit = new boolean[n][m];
		
		// map == 1 : 치즈, map == 2 : 외부공기, map == 0 : 내부공기
		for(int i = 0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<m; j++) {
				int info = Integer.parseInt(st.nextToken());
				map[i][j] = info;
			}
		}
		int result = 0;
		while(true) {
			if(isDeleteAll())
				break;
			result++;
			checkOutSideAir(0,0);
			initVisit();
			deleteCheese();
		}
		
		System.out.println(result);
	}
	// 치즈가 전부 삭제되었는지 확인하는 메서드
	public static boolean isDeleteAll() {
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(map[i][j] == 1)
					return false;
			}
		}
		return true;
	}
	// dfs 탐색으로 외부 공기의 위치 파악 메서드
	public static void checkOutSideAir(int x, int y) {
		visit[x][y] = true;
		map[x][y] = 2;
		
		for(int i = 0; i<4; i++) {
			int nextX = x+dx[i];
			int nextY = y+dy[i];
			
			if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;
			if(map[nextX][nextY] == 1 || visit[nextX][nextY])
				continue;
			
			checkOutSideAir(nextX, nextY);
		}
	}
	// 치즈 삭제 메서드
	public static void deleteCheese() {
		Queue<int[]> q = new LinkedList<>();
		
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				// 해당 위치가 치즈이고
				if(map[i][j] == 1) {
					if(isDeleteCheese(i,j))
						q.offer(new int[] {i,j});
				}
				
			}
		}
		
		// 치즈 삭제
		while(!q.isEmpty()) {
			int[] deletePos = q.poll();
			int x = deletePos[0];
			int y = deletePos[1];
			map[x][y] = 0;
		}
				
	}
	// 방문 초기화 메서드
	public static void initVisit() {
		for(int i = 0; i<n; i++) {
			Arrays.fill(visit[i], false);
		}
	}
	// 삭제될 치즈인지 확인하는 메서드
	public static boolean isDeleteCheese(int x, int y) {
		int count = 0;
		for(int i = 0; i<4; i++) {
			int nextX = x+dx[i];
			int nextY = y+dy[i];
			if(map[nextX][nextY] == 2)
				count++;
		}
		
		if(count >= 2)
			return true;
		else
			return false;
	}
}