[ 백준 2638 ] 치즈 (C++)

 

 

2638번: 치즈

 

 

 

문제!

---

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

......

 

---

요약하면

1. 바깥공기와 접한 부분이 2변이상이 되는 치즈는 1시간이 지나면 모두 녹는다

2. 치즈 내부에도 공기가 차있을 수 있다.

3. 가장자리에는 치즈를 배치하지 않는다

4. 모든 치즈가 녹는 시간은 언제인가?

 

 

예를 들어 아래와 같은 치즈가 있다고 하면

	치즈	치즈	치즈
	치즈		치즈
	치즈	치즈	치즈

먼저 각 끝점 4개의 치즈가 2변씩 공기에 노출되어있어 

녹을것입니다.

 

 

그렇게 아래처럼 녹게되면 이제 각 치즈는 3변이 바깥공기에 노출되어 

녹게됩니다. 

		치즈
	치즈		치즈
		치즈

 

이제 모든 치즈가 녹아버리게 되고 , 시간은 2시간 걸리게 됩니다!

 

 

 

 

문제 이해는 끝났는데 어떻게 풀어야할까...

구해야되는 것들을 생각해보니 쉽게 풀어낼 수 있었습니다!

 

 

구해야 할 것을 나열해 보면

 

1. 바깥 공기의 영역

2. 각 치즈의 노출된 변의 갯수

 

이렇게 2개 정도만 구해주면 될 것 같습니다. 

 

 

여기서 공기의 영역은 탐색을 통해 찾아가고,

탐색을 하는 도중에 만난 치즈들에 노출된 변의 갯수를 책정해 주는 방식으로 풀어 보았습니다. 

 

 

바로

 

코드!

---

선언부에서는 

치즈의 위치를 담을 cheese

노출 정도를 담을 exposed

공기의 영역을 담을 Air

 

이렇게 3개를 중점으로 선언해 주었습니다. 

int N, M;

// 우선 탐색으로 외부공기의 영역 표시
// 2면이 노출된 부분도 표시

//1시간뒤 소멸시키고 다시 탐색 & 영역표시 
//계속 소거


int cheese[102][102]={0};
int exposed[102][102] = { 0 };
int Air[102][102] = { 0 };


int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 }; // 상하 좌우

 

다음은 입력!

cin >> N >> M;

	int cheeseCount = 0;
	int Time = 0;
	for (int i = 0; i <= N+1; i++) {
		for (int j = 0; j <= M+1; j++) {
			if (i == 0 || j == 0 || i == N + 1 || j == M + 1) {
				cheese[i][j] = 3;  // 테두리
			}
			else {
				cin >> cheese[i][j];
				if (cheese[i][j]==1) {
					cheeseCount += 1;
				}
			}
		}
	}

여기서 저는 

 

아래처럼 이동가능한지 확인하는 if문 대신

if(movey>=0 && movey<=N+1 && movex >= 0 && movex <= M + 1){

......

 

 

테두리를 미리 쳐두어

아래처럼 확인하도록 하는 방식으로 만들어 보기위해 

if (cheese[movey][movex]!=5){
.....

각 끝테두리의 cheese는 3으로 선언해주었습니다. 

 

그럼 아래처럼 주어진 치즈 박스가 3으로 둘러쌓인채로 만들수 있습니다. 

(이렇게 하면 편하긴 한데 메모리 소비와 나중에 index값을 헷갈릴 수도 있기에.... 원래 방법을 사용합시다!)

 

 

 

다음은 공기의 영역을 파악하기위한 bfs를 만들어 주었습니다. 

시작은 1,1에서 갈 수 있는 모든 영역에 대해 탐색을 해주어 Air를 최신화시켜 주었습니다. 

void bfs() { // 시작은 1,1
	queue<pair<int, int>> temp; 

	Air[1][1] = 1;
	temp.push({ 1,1 });


	while (!temp.empty()) {
		int tempy = temp.front().first;
		int tempx = temp.front().second;


		temp.pop();

		for (int i = 0; i < 4; i++) {
			int movey = dy[i] + tempy;
			int movex = dx[i] + tempx;

			
			if (cheese[movey][movex]!=3 && Air[movey][movex] == 0) { // 공기탐색
				if (cheese[movey][movex] == 1 ) {
					exposed[movey][movex] += 1;// 공기노출
				}
				else {
					Air[movey][movex] = 1;
					temp.push({ movey ,movex });

				}
			}
		}
	}
}

 

 

 

탐색 도중 치즈를 만나게 되면 아래처럼 exposed 값을 +1 해주어 얼마나 노출되었는지도 체크해주었습니다.

if (cheese[movey][movex] == 1 ) {
    exposed[movey][movex] += 1;// 공기노출
}

 

 

 

마지막으로 while문을 통해 모든 치즈가 없어질때까지 [공기탐색 >> 치즈녹임] 을 반복하면서 시간을 체크해 주었습니다. 

while (cheeseCount != 0) {
    Time += 1;
    bfs();

    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= M + 1; j++) {
            if (exposed[i][j] >= 2) {
                cheeseCount -= 1;
                cheese[i][j] = 0;
            }

            exposed[i][j] = 0;
            Air[i][j] = 0;
        }
    }

}

여기서 exposed, Air값은 항시 초기화 시켜 주었습니다. 

 

 

 

exposed, Air값을 초기화 시켜주는 것이 시간초과를 일으킬까 걱정했는데 다행히 이 문제에서는 통과 할 수 있었습니다.

 

 

 

 

이번 문제를 통해 배운 내용

1. 문제에 겁먹지 말자, 구해야하는 값을 생각해보고 어떻게 효율적으로 구할지 생각하자

 

 

알고리즘에 대해서는 없네요....

생각보다 쉽게 풀린 문제였습니다!

 

 

 

 

그럼 끝!

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>

using namespace std;

int N, M;
// 우선 탐색으로 외부공기의 영역 표시
// 2면이 노출된 부분도 표시

//1시간뒤 소멸시키고 다시 탐색 & 영역표시 
//계속 소거

int cheese[102][102]={0};
int exposed[102][102] = { 0 };
int Air[102][102] = { 0 };

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 }; // 상하 좌우

void bfs() { // 시작은 1,1
	queue<pair<int, int>> temp; 

	Air[1][1] = 1;
	temp.push({ 1,1 });

	while (!temp.empty()) {
		int tempy = temp.front().first;
		int tempx = temp.front().second;
		temp.pop();

		for (int i = 0; i < 4; i++) {
			int movey = dy[i] + tempy;
			int movex = dx[i] + tempx;

			if (cheese[movey][movex]!=3 && Air[movey][movex] == 0) { // 공기탐색
				if (cheese[movey][movex] == 1 ) {
					exposed[movey][movex] += 1;// 공기노출
				}
				else {
					Air[movey][movex] = 1;
					temp.push({ movey ,movex });

				}
			}
		}
	}
}


int main() {
	cin >> N >> M;

	int cheeseCount = 0;
	int Time = 0;
	for (int i = 0; i <= N+1; i++) {
		for (int j = 0; j <= M+1; j++) {
			if (i == 0 || j == 0 || i == N + 1 || j == M + 1) {
				cheese[i][j] = 3;  // 테두리
			}
			else {
				cin >> cheese[i][j];
				if (cheese[i][j]==1) {
					cheeseCount += 1;
				}
			}
		}
	}

	while (cheeseCount != 0) {
		Time += 1;
		bfs();
		for (int i = 0; i <= N + 1; i++) {
			for (int j = 0; j <= M + 1; j++) {
				if (exposed[i][j] >= 2) {
					cheeseCount -= 1;
					cheese[i][j] = 0;
				}
				exposed[i][j] = 0;
				Air[i][j] = 0;
			}
		}
	}

	cout << Time << "\n";
	return 0;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!