백준 2636 <치즈>

기본 완전 탐색으로 풀어도 통과가 되는 골드 5 수준의 문제이다.

 

치즈가 전체 꽉 차 있더라도 치즈가 녹는 시간은 가장 n과 m 중 큰 수의 1/2 그리고 접체 맵의 크기만큼 n*m이므로

n*m*(최대)/2 이므로 50만이 최대이기때문에 시간 초과는 날 수 없다.

 

그러나 맵 크기만큼인 최대인 10000번 으로 끝내는 방법으로 구성했다.

 

 풀이 방법

1. 0,0 지점은 치즈 가 존재하지 않기 때문에 bfs를 진행하며 visit처리를 하고 1 즉 치즈가 위치 한 곳이면 list라는 큐에 넣어 주었다.
2. 가장 끝점의 치즈가 list에 담겨있을 것이고 여기서 Queue를 제거하면서 방문하지 않은 1이면 다시넣어주고 방문하지 않은 0이면 즉 --> 구멍이기 때문에 bfs를 수행해 list에 담아 주었다.
3. list가 빌때까지 진행하며 비었을 경우 return 한다.

 

이렇게 전체의 치즈를 list에 담아줬다.

치즈가 4방향으로 가면서 빈공간일 경우 즉 화살표처럼 구멍인 곳이기 때문에 BFS를 진행해

저 부분을 list에 추가 해준다 

 

이렇게 list가 빌때까지 진행하여 t를 출력하는 것이다.

 

전체 코드

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int map[][],dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},t,n,m,last;
	static boolean visit[][];
	static Queue<Point> q,list;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		list=new LinkedList<Point>();//가장 자리 치즈 담을것
		q=new LinkedList<Point>();
		n = Integer.parseInt(st.nextToken());
		m= Integer.parseInt(st.nextToken());
		map = new int[n][m];
		visit=new boolean[n][m];
		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());
			}
		}
		
	
		find();//가장끝에있는 치즈 찾기
		if(!list.isEmpty()) {//치즈가 하나라도 존재함
			time();
		}
		System.out.println(t);
		System.out.println(last);
		
	}
	private static void find() {
		// TODO Auto-generated method stub
        q.add(new Point(0,0);
        visit[0][0]=true;
		while(!q.isEmpty()) {
			Point next=q.remove();
			for(int i=0;i<4;i++) {
				int x=next.x+dir[i][0];
				int y=next.y+dir[i][1];
				if(x<0||y<0||x>=n||y>=m||visit[x][y]) {
					continue;
				}
				visit[x][y]=true;
				if(map[x][y]==1) {
					list.add(new Point(x,y));
				}
				else {
					q.add(new Point(x,y));
				}
			}
		}
	}
	private static void time() {
		// TODO Auto-generated method stub
		while(true) {
			int num=list.size();
			last=num;
			int nu=0;
			while(nu<num) {
				Point next=list.remove();
				for(int i=0;i<4;i++) {
					int x=next.x+dir[i][0];
					int y=next.y+dir[i][1];
					if(x<0||y<0||x>=n||y>=m||visit[x][y]) {
						continue;
					}
					visit[x][y]=true;
					if(map[x][y]==1) {
						list.add(new Point(x,y));
					}
					else {//0인데 방문하지 않은곳 -->안에있는 빈칸
						def(x,y);
					}
				}
				nu++;
			}
			t++;
			if(list.isEmpty()) {
				return;
			}
		}
	}
	private static void def(int x1, int y1) {
		// TODO Auto-generated method stub
		Queue<Point> kin=new LinkedList<Point>();
		kin.add(new Point(x1,y1));
		while(!kin.isEmpty()) {
			Point next=kin.remove();
			for(int i=0;i<4;i++) {
				int x=next.x+dir[i][0];
				int y=next.y+dir[i][1];
				if(x<0||y<0||x>=n||y>=m||visit[x][y]) {
					continue;
				}
				visit[x][y]=true;
				if(map[x][y]==1) {
					list.add(new Point(x,y));
				}
				else {
					kin.add(new Point(x,y));
				}
			}
		}
	}

}