[백준] G4 2638 치즈 (java)

www.acmicpc.net/problem/2638

2638번: 치즈

 

풀이

 

1) 방문체크를 위한 int형 2차원 배열 check[r][c] 가 필요하다. 방문했을 시 1을 저장한다.

2) (0,0)은 항상 공기이므로 계속 (0,0) 에서만 bfs를 돌릴것이다.  <- 치즈가 다 녹을때까지

• check배열을 초기화한다.
• bfs를 돌려서 나온 배열을 통해 만약 map의 4방향을 더해서 2 이상이면 치즈를 녹일거임
• 하지만 전부 계산하고 녹여야함. 중간에 먼저 녹이면 값이 달라짐. 고로 temp를 사용한다.
• 한 사이클이 돌면 t를 1증가 시킨다.

3) 모든 사이클이 끝나면(더이상 녹을 치즈가 없다면) 시간을 출력한다.

 

주의사항

 

1) memoization

 

package com.baekJoon;

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

public class BJ_G4_2638_치즈 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,map[][],check[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new int[N][M];
		check = new int[N][M];
		// 새로 생성, 0으로 초기화 둘중 누가 빠른지 해보자
		
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		int t=0;
		while(remainIce()) {
			for(int r=0; r<N; r++) {
				for(int c=0; c<M; c++) {
					check[r][c] = 0;
				}	
			}
			bfs(0,0);
			melt();
			t++;
		}
		System.out.println(t);
	}

	private static void melt() {
		int temp[][] = map.clone();
		for(int r=0; r<N; r++) {
			for(int c=0; c<M; c++) {
				if(temp[r][c] == 1 ) {
					int sum = 0;
					for(int d=0; d<4; d++) {
						int nr = r+dr[d];
						int nc = c+dc[d];
						sum += check[nr][nc];
					}
					if(sum>=2) {
						map[r][c] = 0;
					}
				}
			}	
		}
	}

	private static void bfs(int r, int c) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(r, c));
		check[r][c] = 1;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && check[nr][nc] != 1 && map[nr][nc] == 0) {
					check[nr][nc] = 1;
					queue.offer(new Node(nr, nc));
				}
			}
			
		}
	}

	private static boolean remainIce() {
		
		for(int r=0; r<N; r++) {
			for(int c=0; c<M; c++) {
				if(map[r][c] == 1) {
					return true;
				}
			}	
		}
		return false;
	}
	
	static class Node{
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}

	static String src =
			"8 9\r\n" + 
			"0 0 0 0 0 0 0 0 0\r\n" + 
			"0 0 0 1 1 0 0 0 0\r\n" + 
			"0 0 0 1 1 0 1 1 0\r\n" + 
			"0 0 1 1 1 1 1 1 0\r\n" + 
			"0 0 1 1 1 1 1 0 0\r\n" + 
			"0 0 1 1 0 1 1 0 0\r\n" + 
			"0 0 0 0 0 0 0 0 0\r\n" + 
			"0 0 0 0 0 0 0 0 0";
}

 

 

후기

 

 이 문제는 3 달전 보자마자 걸렀던 문제였다. 하지만 지금의 나는 보자마자 풀수 있게되었다.

성장했음을 느낀다는것은 정말 보람찬 일이다.

참고로 위의 결과는 위의 사진은 반복할 때마다 check배열을 새로 생성할 경우(아래)와 0으로 세팅할 경우(위)이다.

결과 : 시간차이는 없지만 메모리차이가 조금 있다.