BOJ
BOJ::2638 치즈
BOJ Gold 4
BOJ::2638 치즈
- Link : BOJ::2638 치즈
- Level : Gold 4
- tag : bfs
시사점
- 치즈를 녹이는 문제입니다.
- 눈여겨 봐야할 점은, bfs를 계속 다시 처음부터 돌릴 것인지, 녹은 지점을 시작점으로 돌릴 것인지 입니다.
- 제 풀이상 후자의 경우, 조건 처리가 까다롭습니다.
- 전자로 naive하게 풀이하여도 시간내에 충분합니다.
이해(x)
- 치즈와 공기로 나누어진 맵이 주어집니다.
- 외부 공기 2칸 이상과 인접한 치즈는 1시간 후에 녹습니다.
- 이때, 몇시간 후에 모든 치즈가 녹는지 출력합니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- O(NM) * 최대 시간(100초)
시간 복잡도
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(x)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<bits/stdc++.h>
#define pb push_back
#define rep(i, a, b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
using namespace std;
const int MAXNM = 100 + 4;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
int n, m;
int a[MAXNM][MAXNM];
queue<pair<int,int> > q;
int cnt[MAXNM][MAXNM];
bool seen[MAXNM][MAXNM];
void input(){
cin >> n >> m;
rep(i, 0, n+2){
rep(j, 0, m+2){
if(i == 0 || j == 0 || i == n+1 || j == m+1){
a[i][j] = 0;
continue;
}
cin >> a[i][j];
}
}
}
bool over(int x, int y){return (x<0 || y<0 || x>=n+2 || y>=m+2);}
void bfs(){
rep(tm, 0, 100 + 100){
q.push({0, 0});
memset(seen, false, sizeof(seen));
memset(cnt, 0, sizeof(cnt));
int changed = 0;
while(!q.empty()){
int x = q.front().first, y = q.front().second; q.pop();
rep(i, 0, 4){
int nx = x+dx[i], ny = y+dy[i];
if(over(nx, ny) || seen[nx][ny]) continue;
if(a[nx][ny] == 1){
cnt[nx][ny]++;
if(cnt[nx][ny] == 2){
a[nx][ny] = 0, changed++;
seen[nx][ny] = true;
}
}else{
seen[nx][ny] = true;
q.push({nx, ny});
}
}
}
if(changed == 0){
cout << tm << endl;
return;
}
}
}
void process(){
input();
bfs();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.