[백준] 2638 치즈 - BFS + 시간초과 JAVA

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

2638번: 치즈

코드설명

BFS 문제입니다.

 

 

처음에 풀었을때 메모리초과가 났습니다. 제가 예상하기로는 Queue 2개를 사용하여서 위치를 계속 가지고 있는것이 문제인가 싶었지만, 

문제는 외부 공기인지 체크하는것에 있었습니다.

가장자리는 무조건 비어있으므로 (0,0) 에서 BFS_Set_Air를 통해 현재 치즈에서 외부공기라면 true를 내부공기라면 false로 선언하여 진행합니다. 이 경우, 연산의 시작에서 한번만 실행하면 됩니다.

 

하지만, 처음에 진행한 코드는 BFS_Set_Air를 각 치즈의 연산마다 실행하여 Queue에 너무 많은 값들이 들어가서 오버플로우가 날 수 밖에 없었습니다.

그래서, 매번 치즈의 연산마다 진행하는것이 아닌 각 치즈의 연산이 시작되기 전에 BFS_Set_Air 를 실행하여 외부공기와 내부공기를 정하고 들어가면 메모리초과가 해결되었습니다.

( 쓸데없는 연산을 줄여서 메모리초과와 시간초과를 둘 다 해결해야 합니다. )

 

문제예시

8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0

answer
3

 

코드

정답코드(BFS를 연산전에 해두어서 외부공기와 내부공기의 기준을 한번의 연산으로 설정)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] map;
	public static boolean[][] outerAirCheck;
	public static Queue<Node> cheezeQ = new LinkedList<>();
	public static Queue<Node> newQ = new LinkedList<>();
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
    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];
    	outerAirCheck = 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());
    			
    			if(map[i][j] == 1) {
    				cheezeQ.add(new Node(i, j));
    			}
    		}
    	}
    	
    	if(cheezeQ.isEmpty()) {
    		System.out.println(answer);
    		return ;
    	}
    		
    	simulate();
    	System.out.println(answer);
    }
    
    public static void simulate() {
    	
    	while(true) {
    		
    		newQ.clear();
    		BFS_Set_Air(); //외부공기라면, outerAirCheck == true, 만약에 내부공기라면 false입니다.
        	while(!cheezeQ.isEmpty()) {
        		Node temp = cheezeQ.poll();
        		int r = temp.r;
        		int c = temp.c;
        		int meltingCnt = 0;
        		
        		for(int dir=0;dir<4;dir++) {
        			int nr = r + dx[dir];
        			int nc = c + dy[dir];
        			
        			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; //범위를 벗어나면 넘어갑니다.
        			if(map[nr][nc] == 1) continue; //치즈라면 넘어갑니다.
        			if( map[nr][nc] == 0 && outerAirCheck[nr][nc] == true) { //해당 map[nr][nc]가 외부공기로 파악되는지도 파악합니다.
        				meltingCnt += 1;
        			}
        			
        		}
        		if(meltingCnt >= 2) { //녹을치즈라면 아무처리하지 않습니다.
        			
        		}else if(meltingCnt < 2){ //녹지 않은 치즈라면 계속 가지고있어서 검사합니다.
        			//여기서 BFS로 외부공기와 접촉하지 않는 치즈인지 검사합니다.
    				newQ.add(new Node(r, c));	
        		}
        	}
        	
        	answer += 1;
        	
        	if(!newQ.isEmpty()) { //만약 녹지 않은 치즈가 존재한다면 cheezeQ에 newQ를 대입합니다.
        		cheezeQ.clear();
        		for(int i=0;i<N;i++) {
        			for(int j=0;j<M;j++) {
        				map[i][j] = 0;
        			}
        		}
        		
        		while(!newQ.isEmpty()) {
        			Node temp = newQ.poll();
        			map[temp.r][temp.c]= 1;  //새로운 치즈의 위치로 저장
        			cheezeQ.add(new Node(temp.r, temp.c)); //치즈에 새로운 치즈 삽입
        		}
        		
        	}else {
        		break;
        	}
        	
        	
    	}

    	
    	
    }
    
    public static void BFS_Set_Air() {
    	Queue<Node> q = new LinkedList<Node>();
    	outerAirCheck = new boolean[N][M];
    	outerAirCheck[0][0] = true;
    	q.offer(new Node(0,0));
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nr][nc] == 1) continue; //만약 치즈라면 멈춤. 
    			if(outerAirCheck[nr][nc] == true) continue;
    			outerAirCheck[nr][nc] = true;
    			q.offer(new Node(nr, nc));
    		}
    	}
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

 

 

 

처음에 메모리초과가 난 코드입니다. ( 모든 치즈의 외부를 확인할때마다 BFS를 실행하여 과도하게 많은 Queue가 생성되었습니다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] map;
	public static boolean[][] visited;
	public static Queue<Node> cheezeQ = new LinkedList<>();
	public static Queue<Node> newQ = new LinkedList<>();
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
    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];
    	visited = 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());
    			
    			if(map[i][j] == 1) {
    				cheezeQ.add(new Node(i, j));
    			}
    		}
    	}
    	
    	if(cheezeQ.isEmpty()) {
    		System.out.println(answer);
    		return ;
    	}
    		
    	
    	simulate();
    	System.out.println(answer);
    }
    
    public static void simulate() {
    	
    	while(true) {
    		newQ.clear();
        	
        	while(!cheezeQ.isEmpty()) {
        		Node temp = cheezeQ.poll();
        		int r = temp.r;
        		int c = temp.c;
        		int meltingCnt = 0;
        		
        		
        		
        		for(int dir=0;dir<4;dir++) {
        			int nr = r + dx[dir];
        			int nc = c + dy[dir];
        			
        			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; //범위를 벗어나면 넘어갑니다.
        			if(map[nr][nc] == 1) continue; //치즈라면 넘어갑니다.
        			
        			if( map[nr][nc] == 0 && BFS(new Node(nr, nc))) { //해당 map[nr][nc]가 외부공기로 파악되는지도 파악합니다.
        				meltingCnt += 1;
        			}
        			
        		}
        		if(meltingCnt >= 2) { //녹을치즈라면 아무처리하지 않습니다.
        			
        		}else { //녹지 않은 치즈라면 계속 가지고있어서 검사합니다.
        			//여기서 BFS로 외부공기와 접촉하지 않는 치즈인지 검사합니다.
    				newQ.add(new Node(r, c));	
        		}
        	}
        	
        	answer += 1;

        	if(newQ.isEmpty()) {
        		break;
        	}
        	
        	else if(!newQ.isEmpty()) { //만약 녹지 않은 치즈가 존재한다면 cheezeQ에 newQ를 대입합니다.
        		
        		for(int i=0;i<N;i++) {
        			for(int j=0;j<M;j++) {
        				map[i][j] = 0;
        			}
        		}
        		
        		while(!newQ.isEmpty()) {
        			Node temp = newQ.poll();
        			map[temp.r][temp.c]= 1;  //새로운 치즈의 위치로 저장
        			cheezeQ.add(new Node(temp.r, temp.c)); //치즈에 새로운 치즈 삽입
        		}
        		
        	}
        	
        	
    	}

    	
    	
    }
    
    public static boolean BFS(Node start) {
    	Queue<Node> q = new LinkedList<Node>();
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
				visited[i][j] = false;	
    		}
    	}
    	visited[start.r][start.c]= true; 
    	q.offer(start);
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		
    		//가장자리면 바로 중단시킵니다.
    		
    		
    		if(r == 0 || r == N-1 || c == 0 || c == M-1) { //만약 [0][0]까지 간다면 외부 공기에 덮어씌어지지 않은것입니다.
    			return true;
    		}
    		
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nr][nc] == 1) continue; //만약 치즈라면 멈춤. 
    			if(visited[nr][nc] == true) continue;
    			
    			visited[nr][nc] = true;
    			q.offer(new Node(nr, nc));
    		}
    	}
    	return false;
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}