[C++] 백준 2638번 치즈

2638번: 치즈

구현 / 시뮬레이션 / 그래프 탐색 문제.

문제에서 구현하라는 대로 구현해서 풀면된다.

제출하고 시간이 44ms가 나왔는데, 다른 사람들은 보통 12 ~ 20ms가 나온 것 같았다.

유의미한 차이는 아니라서 일단은 그냥 넘어갔다.

 

문제풀이

문제의 조건들은 다음과 같다.

• 격자의 가장자리들에는 치즈가 존재하지 않는다.
• 한 시간마다 외부공기와 동, 서, 남, 북 중 두 방향 이상 외부공기와 접한 치즈는 녹는다.
• 치즈로 둘러쌓인 공간은 외부 공간으로 치지 않는다.

위 조건들을 종합해서 정리하면 한 시간마다 아래와 같은 순서로 이뤄지면 된다.

1. 외부공기의 시작을 (1, 1)로 BFS를 한다. 어차피 가장자리들에는 치즈가 없다.
   그리고 치즈를 만나면 해당 칸의 치즈에 외부와 접한 면의 수를 +1 시키고,
   외부 다른 공기를 만나면 큐에 넣고 다른 외부 공기로 다시 탐색한다.
2. 기록해놓은 치즈들의 외부와 접한 면의 수를 토대로 2 이상인 것들을 조사한다.
3. 외부와 접한 면의 수가 2 이상인 치즈들을 녹여서 없앤다.
4. 현재 치즈의 수가 0보다 크다면 1로 돌아가고, 0이라면 현재까지 지난 시간을 출력하면 된다.

 

이제 코드를 살펴보자.

 

사용한 STL과 변수

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int height, width;
int board[101][101];
int externalAdjCnt[101][101];
queue<pair<int, int>> externalVisitQ;
vector<pair<int, int>> cheeseVec;
bool visit[101][101];
pair<int, int> direction[4] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};
int ans;

• height, width : 입력받는 N, M이다.
• board 배열 : 빈 칸(0), 치즈(1)
• externalAdjCnt 배열 : 각 치즈인 칸만 고려해서 외부 공기와 몇 면 맞대어 있는지 저장하는 배열
• externalVisitQ : 그래프 탐색을 한 외부 공기 좌표를 넣어두는 큐. 초기화를 하기위해 만듦.
• cheeseVec : 현재 치즈의 좌표를 넣어둠.
• visit 배열 : 그래프 탐색 시 방문여부를 저장해두는 배열
• direction 배열 : 동, 서, 남, 북 저장을 위해 만들어두는 배열
• ans : 결과값

 

메인함수

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> height >> width;

	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) {
				cheeseVec.push_back({ i, j });
			}
		}
	}

	if (cheeseVec.size() != 0) {
		go(1);
	}

	cout << ans;

	return 0;
}

N, M을 입력받고 격자의 정보들을 입력받는다.

만일 격자 정보가 1이라면 치즈벡터에 좌표를 저장해둔다.

그리고 치즈벡터의 사이즈가 0이 아닌 경우, 즉 치즈가 있을 때만 go()메서드를 호출한다.

go()메서드는 위에서 설명한 1 ~ 4 로직을 실행하는 메서드이다.

매개변수 1이 넘어간 것은 최초에는 1시간 지난 경우로 만들겠다는 의미이다.

 

모두 끝나면 ans를 출력한다.

 

시간동안 녹일 치즈를  찾아서 녹이는 메서드

void go(int hr) {
	bfs();
	findMeltCheese();
	if (cheeseVec.size() != 0) {
		go(hr + 1);
	}
	else {
		ans = hr;
		return;
	}
}

• bfs() 메서드 : 외부공기 (1, 1)을 시작으로 외부공기들만 탐색하고,
  치즈를 만나면 해당 치즈가 접한 외부공기 면의 수를 + 1한다.
  

  void bfs() {
  	while(!externalVisitQ.empty()) {
  		int r = externalVisitQ.front().first;
  		int c = externalVisitQ.front().second;
  		externalVisitQ.pop();
  		visit[r][c] = false;
  	}
  
  	queue<pair<int, int>> q;
  	visit[1][1] = true;
  	q.push({ 1,1 });
  	externalVisitQ.push({ 1,1 });
  	while (!q.empty()) {
  		int r = q.front().first;
  		int c = q.front().second;
  		q.pop();
  
  		for (pair<int, int> dir : direction) {
  			int nxtR = r + dir.first;
  			int nxtC = c + dir.second;
  			if (nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width ||
  				visit[nxtR][nxtC]) {
  				continue;
  			}
  
  			if (board[nxtR][nxtC] == 0) {
  				visit[nxtR][nxtC] = true;
  				q.push({ nxtR, nxtC });
  				externalVisitQ.push({ nxtR, nxtC });
  			}
  			else {
  				externalAdjCnt[nxtR][nxtC]++;
  			}
  		}
  	}
  }​

   맨 처음에 externalVisitQ가 빌 때까지 visit배열을 초기화한다.
  지난 시간에 그래프 탐색한 기록을 초기화하는 것이다.
  동, 서, 남, 북 방향으로 다음 칸을 확인하며 다음 칸이 치즈인지,
  외부공기인지에 따른 로직으로 구현해준다.
  
  
• findMeltCheese() 메서드 : 외부 공기와 접한 면의 수가 2 이상인 치즈들을 찾아서 지워주는 메서드.
  

  void findMeltCheese() {
  	for (int i = 0; i < cheeseVec.size(); i++) {
  		int r = cheeseVec[i].first;
  		int c = cheeseVec[i].second;
  		if (externalAdjCnt[r][c] >= 2) {
  			cheeseVec.erase(cheeseVec.begin() + i);
  			board[r][c] = 0;
  			i--;
  		}
  		externalAdjCnt[r][c] = 0;
  	}
  }​

  현재 치즈의 좌표를 저장하는 벡터에서 좌표를 가져와서 해당 치즈가 몇 면의 외부공기와 접하는지 확인한다.
  만일 2면 이상이라면 벡터에서 지우고 격자에서 해당 좌표를 0으로 바꾼다.
  벡터의 사이즈도 1 작아졌으므로 i도 1빼준다.
  마지막으로 외부면과 맞닿은 수를 확인했으므로 초기화도 여기서 진행해준다.
  
  

설명하면서 불필요한 정보를 지웠더니 시간이 줄었다.

이상하게 메모리는 올라갔다. 왜인지는 모르겠다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.