[백트레킹] 2636번 치즈

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

※문제 어떻게 풀지?※

조건

1. 한 시간이 지나면 공기와 접한 부분은 녹는다.

2. 맨가 쪽은 없는 부분

3. 다 녹기 전 몇개 남았는지? 계산한다.

문제

치즈 안쪽 구멍은 어떻게 식별하는가?

또는, 밖에서 부터 녹여 들어가면 안되나? 라고 생각을 하게 됬네요 ㅎㅎ.

※필요 역량 정리하기!!!※

1. memset 헤더는 #include<string.h> <= 이걸 안적어주면 백준에서 컴파일 에러납니다.

2. 아직은 "실패"했다고 뜨네요... 좀 더 고민을 해야될 것 같습니다.

/*
2018-10-06
- 2636번 치즈 
*/
 
#include<iostream>
#include<string.h>
using namespace std;
int n, m;
int map[101][101];
int visit[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int day = 0;
 
 
void dfs(int x, int y) {
    visit[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visit[nx][ny] == 0 && map[nx][ny] == 1) { //치즈 녹이는 단계
            visit[nx][ny] = 1; // 방문했으므로 0이어도 방문안하게
            map[nx][ny] = 0; // 녹이기
        }
        else if(visit[nx][ny] == 0 &&map[nx][ny] == 0) //치즈에 도달하지 않았으면 계속 진행
            dfs(nx, ny);
    }
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    int lastcheese;
    while (1) {
        day++;
        memset(visit, 0, sizeof(visit));
        dfs(0, 0); // 벽에서 부터 치즈 녹이면 됨
        int cheese =0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) cheese++;
            }
        } // 치즈 갯수
        if (cheese == 0) {
            cout << day << endl << lastcheese;
            break;
        }
        else {
            lastcheese = cheese;
        }
    }
    
 
    return 0;
}
/*

    return 0;
}