BOJ 2636:: 치즈

2016년 11월 12일

DFS 풀이

먼저 외부 공기와 치즈 내부 구멍을 구분할 필요가 있으니 외부를 0이 아니라 2로 다 바꿔버립시다. 재귀함수 써서 DFS 구현해주면 됩니다. 그리고 반복문을 돌립니다. 먼저 외부 공기(2)와 접촉해있는 치즈(1)를 다 찾은 다음 (2중 for문) 그런 치즈는 녹는다고 했으니까 2로 바꿉니다. 그리고 녹은 치즈와 인접한 칸이 0이면 그 치즈가 녹으면서 외부 공기와 내부 구멍이 만나게 되는 것이므로 아까와 똑같이 DFS를 써서 해당 0과 인접한 0들을 다 2로 놓습니다.

만약 치즈가 한 칸도 없다면 반복문을 종료하고, 그 때까지 반복한 횟수가 녹는데 걸리는 시간이 됩니다. 다 녹기 한 시간 전 치즈 개수는 반복문 돌 때마다 각 시각별로 녹는 치즈 개수를 저장해주면 알 수 있죠. 

#include<iostream>
#include<vector>

using namespace std;

const int Adj[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void fill(vector<vector<int>> &Map, int r, int c) {
    if (r<0 || r>=Map.size() || c<0 || c>=Map[0].size()) return;
    if (Map[r] == 0) {
        Map[r] = 2;
        for (int i=0; i<4; i++) {
            fill(Map, r+Adj[i][0], c+Adj[i][1]);
        }
    }
}

bool canMelt(vector<vector<int>> &Map, int r, int c) {
    int t = 0;
    for (int i=0; i<4; i++) {
        if (Map[r+Adj[i][0]][1]] == 2) t++;
    }
    return t > 0;
}

int main(void) {
    int m, n, time = 0;
    cin >> m >> n;

    vector<vector<int>> Map(m, vector<int>(n));
    for (int i=0; i<m; i++) for (int j=0; j<n; j++) scanf("%d", &Map[i][j]);

    fill(Map, 0, 0);

    vector<vector<int>> MapAlt = Map;

    vector<int> NumMelt;
    while (true) {
        int cnt = 0;
        for (int i=1; i<m-1; i++) {
            for (int j=1; j<n-1; j++) {
                if (Map[i][j]==1 && canMelt(Map, i, j)) {
                    MapAlt[i][j] = 2;
                    cnt++;
                    for (int k=0; k<4; k++) {
                        fill(MapAlt, i+Adj[k][0], j+Adj[k][1]);
                    }
                }
            }
        }
        if (cnt == 0) {
            printf("%d\n%d", time, NumMelt[time-1]);
            break;
        }
        Map = MapAlt;
        NumMelt.push_back(cnt);
        time++;
    }

    return 0;
}

fill은 DFS로 2를 채우는 함수, canMelt는 그 치즈가 외부 공기와 접촉해 있는지 판정하는 함수입니다. 각 시각별로 녹는 치즈 개수를 NumMelt에 저장합니다.

다익스트라 풀이

각 칸을 그래프의 꼭짓점으로 두고 인접한 칸 사이에 방향 있는 변을 양방향으로 놓아줍시다. 변의 가중치는 치즈가 없는 칸으로 가는 변에는 0, 있는 칸으로 가는 변에는 1로 줍니다. 그리고 제일 왼쪽 위 칸을 시작점으로 두고 다익스트라 알고리즘으로 모든 칸에 대한 최단거리를 구합니다. 이 최단거리가 DFS 풀이에서 구했던 해당 칸이 0 또는 1에서 2가 되는데 걸리는 시간입니다. 그럼 다 녹는데 걸리는 시간은 치즈가 있던 칸들의 최단거리 중 최댓값이고 다 녹기 한 시간 전 치즈 개수는 그 최댓값을 최단거리로 하는 원래 치즈가 있던 칸의 개수입니다. 

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

typedef tuple<int, int, int> Tint;

const int INF = 1000000;
const int Adj[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main(void) {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> Map(m, vector<int>(n));
    for (int i=0; i<m; i++) for (int j=0; j<n; j++) scanf("%d", &Map[i][j]);

    vector<vector<int>> Dist(m, vector<int>(n, INF));
    vector<vector<bool>> Visited(m, vector<bool>(n, false));
    priority_queue<Tint, vector<Tint>, greater<Tint>> PriorQ;

    Dist[0][0] = 0;
    PriorQ.push(Tint(Dist[0][0], 0, 0));

    while (!PriorQ.empty()) {
        int r, c;
        do {
            r = get<1>(PriorQ.top());
            c = get<2>(PriorQ.top());
            PriorQ.pop();
        } while (!PriorQ.empty() && Visited[r]);

        if (Visited[r]) break;

        Visited[r] = true;
        for (int i=0; i<4; i++) {
            int nr = r + Adj[i][0];
            int nc = c + Adj[i][1];
            if (nr<0 || nr>=m || nc<0 || nc>=n) continue;
            if (Dist[nr][nc] > Dist[r]+Map[nr][nc]) {
                Dist[nr][nc] = Dist[r]+Map[nr][nc];
                PriorQ.push(Tint(Dist[nr][nc], nr, nc));
            }
        }
    }

    int max = 0;
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (Map[i][j] == 1)
                max = (max>Dist[i][j])?max:Dist[i][j];

    int cnt = 0;
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (Map[i][j]==1 && max==Dist[i][j]) cnt++;

    printf("%d\n%d", max, cnt);

    return 0;
}
PS