[C++, 코딩테스트] Softeer : 동계 테스트 시점 예측 with DFS

 

이 문제는 현대스러운 문제였다. 그래서 푸는데 재밌었다. 처음에는 어떻게 풀어야할지 고민을 좀 했던 것 같다. 하지만 이렇게 맵을 가지고 푸는 문제는 dfs, bfs중에 하나인 경우가 많기 때문에 이 두 알고리즘을 어떻게 적용할지 고민했다.

 

그래서 내가 푼 방식을 dfs를 여러 번 적용하는 방식이다. 일단 모든 외부의 0을 훑어야하고 1과 접촉한 0들이 1에 왔다갔음을 기록해야지 2개 이상이 접촉했음을 알 수 있다.

 

그래서 나는 이미 훑고 간 0은 -1로 바꾸었고 0이 접촉한 1을 +1을 해서 몇개 옆에 붙었는지 카운트하였다.

그래서 3이상의 값을 가진 얼음들은 2개이상이 접촉했기 때문에 1시간 뒤에 얼음이 녹는 것을 확인할 수 있었다.

 

 

 

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> arr;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
int N, M;

void dfs(int x, int y){
    if (arr[y][x] > 0){
        arr[y][x]++;
        return ;
    }
    arr[y][x] = -1;
    for (int i = 0; i < 4; i++){
        int X = x + dx[i];
        int Y = y + dy[i];
        if (X < 0 || X >= M || Y < 0 || Y >= N)
            continue;
        if (arr[Y][X] == -1)
            continue;
        dfs(X, Y);
    }
}

int main(int argc, char** argv)
{
    cin >> N >> M;
    int value;
    vector<int> line;
    for (int i = 0; i < N; i++){ // 맵담기
        for (int j = 0; j < M; j++){
            cin >> value;
            line.push_back(value);
        }
        arr.push_back(line);
        line.clear();
    }

    int hour = 0;

    while (1){
        dfs(0, 0);
        bool end = true;
        for (int y = 0; y < N; y++){
            for (int x = 0; x < M; x++){
                if (arr[y][x] > 2){
                    arr[y][x] = 0;
                    end = false;
                } else if (arr[y][x] > 0) {
                    arr[y][x] = 1;
                    end = false;
                } else if (arr[y][x] == -1) {
                    arr[y][x] = 0;
                }
            }
        }
        if (end)
            break;
        else
            hour++;
    }
    
    cout << hour << endl;
    return 0;
}