문제 이해 단계
https://www.acmicpc.net/problem/2638
NxM 크기의 맵에 1로 표기된 치즈가 있다.
치즈는 외부 공기와 두 번 이상 접촉하면 녹는다.
겉에서부터 치즈가 녹아내릴 때,
모든 치즈가 녹아내리는 데 걸리는 시간을 구하는 문제
문제 접근 단계
문제의 조건부터 살펴보자.
맵의 크기는 최대 100x100까지 가능하다.
맵의 크기는 그렇게 크지 않아서, 탐색을 하기에는 무리가 없을 것 같다.
문제의 유형
문제의 유형을 추측해 볼 때, 2차원 맵이 주어지고,
치즈가 없어지는 조건이 네 면 중 두 변이 접촉해야 하는 것이라고 했다.
이를 그림에서 살펴보면, 1이 없어지기 위해서는 겉에 있는 0과 2개 이상 인접해야 한다.
이를 쉽게 알아내기 위해서는
너비우선탐색(BFS)으로 확인하는 것이 제일 적절하다고 생각했다.
외부 공기와 내부 공기를 어떻게 구분해야 할까?
아마 이 문제의 핵심적인 부분일 것이다.
외부에 있는 공기에 닿은 치즈만 지워져야 하기 때문에 이 구분은 필수적이다.
여기서 생각해봐야 하는 것이 내부 공기가 뜻하는 것이다.
내부 공기는 1로 둘러싸여 있어 폐쇄되어 있다. 즉 외부 공기와 내부 공기는 서로 만날 수 없다.
이를 인지하면서 1 밖에 있는 0을 선택해 주면 되는데,
외부공기끼리 서로 단절되어 있을 수도 있다.
그래서 이를 한 번에 해결해 줄 수 있는 방법이 있다.
임의의 테두리를 하나 더 만들어서 모든 외부 공기 부분을 연결시켜 주는 것이다.
이렇게 하고 BFS를 돌리면 모든 외부 공기 부분이 연결되고, 겉에 있는 1 부분과 모두 접촉할 수 있다.
이런 식으로 BFS를 돌린다.
두 변과 접촉
이 방법은 간단하다.
방문 체크를 해주는 visited 배열을 bool이 아닌 정수형으로 선언해 줘
0만으로 BFS를 할 때 1을 두 번 만난다면, 이 수를 0으로 바꿔주면 된다.
이제 이를 코드로 구현해 보자.
문제 구현 단계
// 맵의 크기 최대값보다 더 크게 선언해줘야함
int map[105][105] = {0,};
int visited[105][105] ={0,};
int N,M;
// bfs
int bfs(){
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
queue<pair<int,int>> q;
// 할때마다 매번 visited 배열 0으로 초기화
fill(&visited[0][0],&visited[104][105],0);
visited[0][0] = 1;
q.push({0,0}); // (0,0)부터 시작
int count = 0; // 카운팅된 치즈의 개수
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 추가된 바깥 테두리까지 포함된 범위
if(nx < 0 || ny < 0 || nx > N+1 || ny > M+1) continue;
// 치즈를 만날 경우 해당 visited배열에 +1을 해줌
if(map[nx][ny] == 1) {
visited[nx][ny]++;
// 해당 칸의 visited배열이 2이상이면 map 값을 0으로 바꿈
if(visited[nx][ny] >= 2) {
map[nx][ny] = 0;
count++;
}
}
// 0이고 방문하지 않은 곳일때만 큐에 추가
else if(map[nx][ny] == 0 && !visited[nx][ny]){
visited[nx][ny] = 1;
q.push({nx,ny});
}
}
}
return count;
}핵심이 되는 전역변수들과 bfs 함수이다.
바깥 테두리를 추가해 줬기 때문에 맵을 기존 범위인 100보다는 큰 범위로 선언해줘야 한다.
visited 배열 또한 정수 2차원 배열로 선언해 준다.
bfs 함수 부분은 시작 좌표를 무조건 (0,0)에서 시작하는 것 이외에는 일반적인 BFS와 큰 차이점이 없다.
굳이 (0,0)에서 시작해 주는 이유는 (0,0)은 확정적으로 치즈가 없는 부분이기 때문이다.
BFS는 간단하다. 0인 부분만 큐에 추가해 주는 것으로 하고 1을 만나면 1인 칸에 있는 visited에 +1을 해준다.
해당 칸의 visited의 값이 2 이상이 되면 2변 이상이 0과 맞닿은 것으로 판단하고 0으로 바꿔준다.
이러한 과정을 큐가 빌 때까지 반복한다.
이러한 모든 과정이 1시간(한번) 동안 일어나는 과정이다.
반환해 주는 것은 count인데, 이는 발견한 치즈의 수이다.
이를 반환해 주는 이유는 남아있는 치즈가 있는지를 확인해 주기 위해서이다.
만약 남아있는 치즈가 없다면, count는 0이 되어 0을 반환할 것이다.
핵심적인 코드에 대한 설명은 여기까지이고, 이제 아래에 전체 코드를 올리고 포스팅을 종료한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 맵의 크기 최대값보다 더 크게 선언해줘야함
int map[105][105] = {0,};
int visited[105][105] ={0,};
int N,M;
// bfs
int bfs(){
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
queue<pair<int,int>> q;
// 할때마다 매번 visited 배열 0으로 초기화
fill(&visited[0][0],&visited[104][105],0);
visited[0][0] = 1;
q.push({0,0}); // (0,0)부터 시작
int count = 0; // 카운팅된 치즈의 개수
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 추가된 바깥 테두리까지 포함된 범위
if(nx < 0 || ny < 0 || nx > N+1 || ny > M+1) continue;
// 치즈를 만날 경우 해당 visited배열에 +1을 해줌
if(map[nx][ny] == 1) {
visited[nx][ny]++;
// 해당 칸의 visited배열이 2이상이면 map 값을 0으로 바꿈
if(visited[nx][ny] >= 2) {
map[nx][ny] = 0;
count++;
}
}
// 0이고 방문하지 않은 곳일때만 큐에 추가
else if(map[nx][ny] == 0 && !visited[nx][ny]){
visited[nx][ny] = 1;
q.push({nx,ny});
}
}
}
return count;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++) cin >> map[i][j];
int count = 0;
int ans = -1;
// count가 0이 될때까지 반복한다.
// 즉, 치즈가 다 녹을때까지 반복한다.
do{
ans++;
count = bfs();
}while(count > 0);
cout << ans;
}
시행착오
예전에 이름도 같고 비슷한 문제를 풀어본 적 있다.
로직도 완전히 비슷해서 20분 만에 풀었다.
그 문제를 풀지 않았다면 골드 3 정도의 난이도인지 모르겠는데,
그 문제를 풀어봤어서 그 정도 난이도 인지를 모르겠다.
생활비..