[BOJ/JAVA] 백준 2636번 : 치즈

2636번: 치즈

 

 

 

 

---

 

 

 

 

• 풀이

 

시간 제한은 1초 입니다. 가로, 세로 최대값이 100인 것을 감안해서 보면 빡빡하지 않은 시간으로 문제설명대로 구현하면 된다고 생각했습니다.

 

문제의 구현 방법은 bfs방식을 사용했습니다.

1. bfs를 통해 (0, 0)에서 0을 타고다니며 0과 인접한 1만 melt라는 queue에 추가시켜주었습니다. (같은 index가 추가되지 않게 배열 하나를 추가로 만들어 중첩을 방지해 주었습니다.)
2. 현재가 마지막 치즈를 녹이는 작업이 될 수 있으므로 size라는 변수를 만들어 melt의 size로 초기화 시켜주었습니다. (만약, melt의 size가 0일경우 초기화 시켜주기 전 반복문을 종료합니다.)
3. 위의 bfs가 종료되면 melt에는 현재 시간에 녹을 치즈의 index만 남아있습니다. melt 큐에 저장된 모든 위치의 치즈인 1을 0으로 바꾸는 작업을 합니다.
4. count변수를 만들어 횟수를 1 증가시켜줍니다.
5. 위의 1~4 작업을 반복합니다.

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
    static int N, M;
    static StringBuilder sb;
    static int[][] array;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] check;
    
	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		M = in.nextInt();
		array = new int[N][M];
		check = new boolean[N][M];
		sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				array[i][j] = in.nextInt();
	
			}
		}
		
		bfs();
	}
	
	private static void bfs() {
		Queue<Node> queue = new LinkedList<>();
		Queue<Node> melt = new LinkedList<>();
		boolean[][] visit = new boolean[N][M];
		int a = 0, b = 0, count = 0, size = 0;
		
		while(true) {
			for(int i = 0; i < N; i++)
				Arrays.fill(check[i], false);
			queue.add(new Node(0, 0));
			check[0][0] = true;
			while(!queue.isEmpty()) {
				Node node = queue.poll();
				
				for(int direction = 0; direction < 4; direction++) {
					int r = node.x + dx[direction];
					int c = node.y + dy[direction];
					
					if(r < 0 || c < 0 || r >= N || c >= M) continue;
					if(check[r][c]) continue;
					if(array[r][c] == 1) {
						if(!visit[r][c]) {
							visit[r][c] = true;
							melt.add(new Node(r,c));
						}
						continue;
					}
					
					queue.add(new Node(r, c));
					check[r][c] = true;
				}
			}
			if(melt.size() == 0) break;
			
			size = melt.size();
			while(!melt.isEmpty()) {
				Node node = melt.poll();
				array[node.x][node.y] = 0;
			}
			
			count++;
		}
		sb.append(count).append("\n").append(size);
	}
}

class Node {
	int x;
	int y;
	
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}