뮁이의 개발새발

[JAVA] 백준 2636,2638 치즈 (BFS, 완전탐색) 본문

Algorithm

[JAVA] 백준 2636,2638 치즈 (BFS, 완전탐색)

뮁뮁이 2021. 9. 15. 14:41

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

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓

www.acmicpc.net

 

정말,, 저의 마음을 속상하게 만든 문제입니다.. 안그래도 BFS 헷갈리는데 나와주고,, 열심히 공부하면서 구현했는데 어딘가에서 알수없는 에러가,, 이것저것 계속 손봐주니까 되긴 했는데 정말 몇시간을 붙잡고 있었는지 모르ㅔㄱㅆ어요 ..

 

문제의 포인트는 안쪽 공기는 0, 바깥쪽 공기는 -1로 바꿔주면서 주변 -1의 갯수로 녹일 치즈일지 판단하는것..!!!

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 bj2636 {

	static class node {
		int x;
		int y;

		public node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	static int[][] map;
	static int[] deltax = { 0, 0, -1, 1 };
	static int[] deltay = { -1, 1, 0, 0 };
	static int N, M;
	static boolean flag;
	static int cheeze = 0;
	static int tempc = 0;

	static LinkedList<node> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					cheeze++;
				}
			}
		}

		int answer = 0;
		while (true) {

			flag = false;
			list = new LinkedList<>(); // 녹일 치즈 들어있는 리스트
			bfs();
			check_melting();
			melting();
//			확인용 출력부분
//			for (int k = 0; k < N; k++) {
//				for (int l = 0; l < M; l++) {
//					System.out.print(map[k][l] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println("*********************************");
			if (flag == true) {
				if (cheeze == 0) {
					break;
				}
				answer++;
			} else {
				break;
			}
		}

		System.out.println(answer + 1);
		System.out.println(tempc);

	}

	static void bfs() {
		Queue<node> queue = new LinkedList<>();
		queue.add(new node(0, 0));

		while (!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.peek().y;
			queue.poll();

			for (int i = 0; i < 4; i++) {
				int nx = x + deltax[i];
				int ny = y + deltay[i];

				if (nx <= -1 || ny <= -1 || ny >= N || nx >= M) {
					continue;
				}
				if (map[ny][nx] != 0) {
					continue;
				}

				if (map[ny][nx] == 0) {
					queue.add(new node(nx, ny));
					map[ny][nx] = -1; // 연결되어있던 공기노출부분 -1로 변경(바깥쪽 공기)
				}

			}

		}

	}

	static void check_melting() {
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < M - 1; j++) {
				if (map[i][j] == 1) {
					int air = 0;
					flag = true;
					for (int k = 0; k < 4; k++) {
						int x = j + deltax[k];
						int y = i + deltay[k];

						if (x <= -1 || y <= -1 || y >= N || x >= M) {
							continue;
						}

						if (map[y][x] == -1) {
							air++;
						}

						if (air >= 1) {
							list.add(new node(j, i));
							break;
						}
					}
				}
			}
		}
	}

	static void melting() {
		tempc = list.size();
		for (int i = 0; i < list.size(); i++) {
			int x = list.get(i).x;
			int y = list.get(i).y;
			map[y][x] = 0;
			cheeze--;
		}

		// 바깥쪽 공기 다시 0으로 바꿔줌
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == -1) {
					map[i][j] = 0;
				}
			}
		}

	}

}

 

+ 자매품 백준 2638번

위의 문제에서 공기노출 갯수를 2 이상으로만 바꿔주면 됨.

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 bj2638 {

	static class node {
		int x;
		int y;

		public node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	static int[][] map;
	static int[] deltax = { 0, 0, -1, 1 };
	static int[] deltay = { -1, 1, 0, 0 };
	static int N, M;
	static boolean flag;
	static int cheeze = 0;
	static int tempc = 0;

	static LinkedList<node> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					cheeze++;
				}
			}
		}

		int answer = 0;
		while (true) {

			flag = false;
			list = new LinkedList<>(); // 녹일 치즈 들어있는 리스트
			bfs();
			check_melting();
			melting();
//			for (int k = 0; k < N; k++) {
//				for (int l = 0; l < M; l++) {
//					System.out.print(map[k][l] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println("*********************************");
			if (flag == true) {
				if (cheeze == 0) {
					break;
				}
				answer++;
			} else {
				break;
			}
		}

		System.out.println(answer + 1);

	}

	static void bfs() {
		Queue<node> queue = new LinkedList<>();
		queue.add(new node(0, 0));

		while (!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.peek().y;
			queue.poll();

			for (int i = 0; i < 4; i++) {
				int nx = x + deltax[i];
				int ny = y + deltay[i];

				if (nx <= -1 || ny <= -1 || ny >= N || nx >= M) {
					continue;
				}
				if (map[ny][nx] != 0) {
					continue;
				}

				if (map[ny][nx] == 0) {
					queue.add(new node(nx, ny));
					map[ny][nx] = -1; // 연결되어있던 공기노출부분 -1로 변경(바깥쪽 공기)
				}

			}

		}

	}

	static void check_melting() {
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < M - 1; j++) {
				if (map[i][j] == 1) {
					int air = 0;
					flag = true;
					for (int k = 0; k < 4; k++) {
						int x = j + deltax[k];
						int y = i + deltay[k];

						if (x <= -1 || y <= -1 || y >= N || x >= M) {
							continue;
						}

						if (map[y][x] == -1) {
							air++;
						}

						if (air >= 2) {
							list.add(new node(j, i));
							break;
						}
					}
				}
			}
		}
	}

	static void melting() {
		tempc = list.size();
		for (int i = 0; i < list.size(); i++) {
			int x = list.get(i).x;
			int y = list.get(i).y;
			map[y][x] = 0;
			cheeze--;
		}

		// 바깥쪽 공기 다시 0으로 바꿔줌
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == -1) {
					map[i][j] = 0;
				}
			}
		}

	}

}

'Algorithm' 카테고리의 다른 글

Floyd 알고리즘 이론 정리  (0) 2021.09.16
[JAVA] SWEA 1263 사람 네트워크 2 (Floyd 알고리즘)  (0) 2021.09.16
[JAVA] 백준 1149 RGB거리 (DP)  (0) 2021.09.15
[JAVA] 백준 1463 1로 만들기 (DP)  (0) 2021.09.14
[JAVA] 프로그래머스 행렬 테두리 회전하기  (0) 2021.09.14
'Algorithm' Related Articles more
Comments