문제

BOJ 2638 치즈🧀

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

계속 알고 풀어야지 풀어야지 했는데 날 유혹하는 수많은 여흥거리들로 인해
흐린 눈..,하며 살다 드!디!어! 문제를 풀었따

사실 이 문제는 풀면서도 아리까리했다
너무 막 푸는 것 같은데 시간 내 가능? 이러면서 확신을 못했는데
테케가 하나밖에 없어서 에라 모르겠다하고 제출했더니 맞았다
얼떨떨하구만ㅋㅋㅋ

사실 코드를 짜는 것보다 문제 풀이를 생각하는 데 시간을 좀 더 소요한 것 같다.
예전엔 이렇게 머리가 안 굳었던 것 같은데...

한 살이라도 젊을 때 대가리를 조금 더 굴려보자!!!🧠🧠

코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj_2638_치즈 {

	static int R,C;
	static int [][] map;
	static boolean[][]out,visit;
	static List<node> list=new ArrayList<>();
	static int answer=0;
	static int [][]dir= {{0,1},{0,-1},{1,0},{-1,0}};
	
	static class node{
		int y,x;
		node(int y,int x){
			this.y=y;
			this.x=x;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		map=new int[R][C];
		out=new boolean[R][C];
		visit=new boolean[R][C];
		
		for(int i=0;i<R;i++) {
			st=new StringTokenizer(br.readLine());
			Arrays.fill(out[i], false);
			for(int j=0;j<C;j++) {
				int a=Integer.parseInt(st.nextToken());
				map[i][j]=a;
				if(a==1) {
					list.add(new node(i,j));
				}
			}
		}
		
		//입력 완
		
		//치즈 안 구멍인지 치즈 밖 구멍인지
		bfs();
		
        //조건에 맞으면 치즈 없애기
		cal();
		
		System.out.println(answer);
		
	}
	
	static void bfs() {
    	
        // 맨 위, 왼쪽은 무조건 빈 칸 (시작점)
		Queue<node>q=new ArrayDeque<>();
		q.add(new node(0,0));
		out[0][0]=true;
		
        // visit 초기화
		for(int i=0;i<R;i++)Arrays.fill(visit[i], false);
		
		visit[0][0]=true;
		
		while(!q.isEmpty()) {
			node nd=q.poll();
	
			for(int i=0;i<4;i++) {
				int ny=nd.y+dir[i][0];
				int nx=nd.x+dir[i][1];
				
				if(ny<0||ny>=R||nx<0||nx>=C||visit[ny][nx]||map[ny][nx]!=0)
					continue;
				q.add(new node(ny,nx));
				out[ny][nx]=true;
				visit[ny][nx]=true;
			}
			
		}
	}
	
	static void cal() {
		
		while(list.size()>0) {
			answer++; 
			for(int k=list.size()-1;k>=0;k--) {
				 int cnt=0;
				 node nd=list.get(k);
                 
				 for(int i=0;i<4;i++) {
					int ny=nd.y+dir[i][0];
					int nx=nd.x+dir[i][1];
					
                    // 치즈 밖인 공간 더하기
					if(out[ny][nx])cnt++;
				 }
				 if(cnt>=2) {
					 list.remove(k);
					 //System.out.println(k);
					 map[nd.y][nd.x]=0;
				 }
			 }
             
             // 치즈가 없어져 새로 생긴 공간 체크
			 bfs();
		}
	}

}

풀이방법

BFS

처음에 이 문제를 접하고는 그냥 구현이네 응응 이게 왜 골3? 이랬는데 치즈 사이의 공간은 밖이라고 취급하지 않는다라는 것을 보고 멘붕쓰....
최솟값, 최댓값을 구하면 어떻게든 되겠지 했는데 하면 할 수록 변수가 너무 많다는 걸 알아버렸다.
그래서 시간이 오래 걸려도 BFS 써서 밖인지 안인지 구분을 하면 되지 않을까? 라는 생각으로 때려 넣었는데 됐다
분명 더 좋은 방법이 있을 텐데 아직 내 뇌에선 나오지 않는다

정신승리도 승리니깐
한 것에 의의를 두고 그럼 안녕~!~~!