[2] BOJ 2636번: 치즈 - DFS

wansuper·2024년 2월 18일

10주 완성 Cpp 코딩 테스트

목록 보기

31/45

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

정답코드

// BOJ 2636번: 치즈
#include <bits/stdc++.h>
using namespace std; 
int a[104][104], visited[104][104];
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};   
int n, m, cnt, cnt2;
vector <pair<int,int>> v;

void go(int y,int x){
    visited[y][x] = 1;		// 1. 무조건 방문을 먼저 찍고
    if(a[y][x] == 1){		// 방문한 곳의 값이 치즈(1)이면 치즈 담는 벡터에 위치 담기
        v.push_back({y,x}); // 2. vector에 넣은 뒤
        return;				// 3. 리턴을 하기 때문에 더 안 쪽에 있는 치즈(1)로 닿지 않는 것!
    }
    for(int i=0; i<4; i++){	// ny,nx 방문 + 방문했으면 패스
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0|| ny>=n||nx<0||nx>=m||visited[ny][nx])continue; // a[ny][nx]가 1이면 v에 담기 위해 pass 조건에서 뺌
        go(ny,nx);
    }
    return;
}
int main(){ 
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    while (true){ 
        fill(&visited[0][0], &visited[0][0] + 104 * 104, 0); // 방문 배열 필요
        v.clear(); 											 // 녹아야할 치즈(1)을 담는 곳 v
        go(0,0); 											 // 시작 위치
        cnt2 = v.size();									 // 치즈가 녹기 전의 시간
        for(pair<int, int> b : v){ 							 // go로부터 완성한 v에 대해 치즈를 녹이는(0) 곳
            a[b.first][b.second] = 0;
        }   
        bool flag = 0;										 // 치즈가 녹아있는지 체크
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] != 0) flag = 1;					 // 치즈가 아직 다 안 녹았으면 flag = 1
            }
        }
        cnt++;												 // 치즈가 녹은 후의 시간++
        if(!flag) break;									 // 치즈가 다 녹아서 flag = 0이면 break
    }
    cout << cnt << '\n' << cnt2 << '\n'; 
}

문제의 Key:

"판의 가장자리엔 치즈가 없다!"

이 말이 있기에, 치즈 없는 부분이 어디있나 따로 찾는 로직이 필요 없어! 가장자리엔 치즈가 없음이 자명하니까!

만약, 이 말이 없다면, 치즈 없는 부분을 찾는 로직이 가장 먼저 나와야 해 (치즈 없는 부분의 위치 따로 저장하고 등등~)

아이디어:

녹기 전의 남은 치즈들의 개수 -> 1의 위치를 저장한 벡터의 size()

1을 만나는 족족 자료구조에 담고 그 값을 0으로 녹이면, 안쪽의 치즈도 녹지 않아?

위치를 담고 return 하기 때문에 1의 위치에서 더 안쪽으로 탐색하지 않는다!

(Tip) 문제에서 '녹인다', '삭제한다' 등이 있을 때, 그 부분을 직접 없앨 수도 있지만, "색칠해가면서" 맵핑을 하는게 낫다!

(맵핑 -> 치즈인 1 -> 0으로 녹이는 아이디어!)

결론:

DFS 탐색

0이면 pass, 1이면 자료구조에 담기. 이 시점이 모두 녹기 전의 시간, cnt2

담은 것들을 0으로 만들기 + 시간++ (다 녹고나서의 시간, cnt)

코드 설명

main() 함수:
// (중략)
while (true){ 
    fill(&visited[0][0], &visited[0][0] + 104 * 104, 0); // 방문 배열 필요
    v.clear(); 						   
    go(0,0); 						   // 시작 위치 (0, 0)
    cnt2 = v.size();				    
    for(pair<int, int> b : v){ 		   // go로 담아둔 치즈(1)를 녹이는(0) 곳
        a[b.first][b.second] = 0;
    }   
    bool flag = 0;					    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] != 0) flag = 1; // 치즈가 아직 다 안 녹았으면 flag = 1
        }
    }
    cnt++;							   
    if(!flag) break;				   // 치즈가 다 녹아서 flag = 0이면 break
}
/*
vector <pair<int,int>> v; // 녹아야할 치즈의 위치(1)를 담는 곳 v
          cnt2            // 치즈가 녹기 전의 시간
          flag            // 치즈가 녹아있는지 체크
          cnt             // 치즈가 녹은 후의 시간
*/
while문에서 치즈가 다 녹았는지 여부를 flag로 검증하면서 녹을 때까지 무한 반복

매 녹는 타이밍마다 visited 배열과 (가장자리 치즈의 위치를 담는) v 벡터는 초기화

시작 위치 (0, 0)으로 설정하고 go 함수 ~ (-> 아직 탐색+위치 저장만 함)

go() 기능: 0인 곳은 방문 처리 + 1인 곳은 해당 위치만 리턴하고 발 빼!

아직 녹은거로 저장 안 한 상태: 녹기 전의 치즈의 개수 (cnt2) 저장

저장한 가장자리 치즈의 위치를 b로 접근하여 0으로 녹임

한 턴 녹이고 다 녹았는지 이중 for문으로 돌면서 확인~

이때의 시간을 cnt로 ++하면 녹는데 걸리는 시간 확인 가능

다 녹았으면 while문 break;

void go() 함수: 가장자리 치즈 위치 담고, 0인 곳 DFS 탐색
void go(int y,int x){
    visited[y][x] = 1;
    if(a[y][x] == 1){		
        v.push_back({y,x}); 
        return;				
    }
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0|| ny>=n||nx<0||nx>=m||visited[ny][nx])continue; // a[ny][nx]가 1이면 v에 담기 위해 pass 조건에서 뺌
        go(ny,nx);
    }
    return;
}
무조건 치즈든, 아니든 방문 먼저 찍고

방문한 곳의 값이 치즈(1)이면 치즈 담는 벡터에 위치 담기 + 리턴으로 go() 종료

그래야 깊숙히 들어가지 않아!

치즈가 아닌 곳(0)에만 탐색! 1인 곳은 종료되었으니까!

1인 곳은 이미 처리했으니, underflow, overflow, 방문한 위치만 pass 처리

go(ny, nx)로 재귀 DFS