백준 2636 : 치즈(bfs/dfs)

 

문제

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

 

• 처음 코드

 

바깥쪽에서 안쪽으로 탐색할때 처음으로 만나는 치즈가 외곽이니 해당 치즈의 갯수를 구하자라는 생각으로 작성..

실패했다

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

// 아이디어 n*m 크기의 보드가 오면 n+2, m+2로 보드를 만들어서 바깥을 두르는 테두리를 만든다
// 테두리의 i = 0 || i = n+1 || j = 0 || j == m+1 지점에서 직선으로 쭉 뻗어서 처음 닿는 부분이 외곽 아닌가?

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n+2,vector<int>(m+2));
    vector<vector<bool>> visited(n+2,vector<bool>(m+2,false));

    for(int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    bool isComplete = false;
    int past = 0;
    int cnt = 0;

    while(!isComplete){
        isComplete = true;

        //좌상단부터 겉에 하나 찾기
        for(int i = 0; i <= n+1; i++){
            for(int j = 0; j <= n+1; j++) {
                // 좌측부터 -> 방향으로 탐색
                if (arr[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    isComplete = false;
                    break;
                }
            }
        }

        for(int i = 0; i <= n+1; i++){
            for(int j = 0; j <= n+1; j++){
                // 좌측부터 아래 방향으로 탐색
                if (arr[j][i] == 1 && !visited[j][i]) {
                    visited[j][i] = true;
                    isComplete= false;
                    break;
                }
            }
        }

        //우상단부터 겉에 하나 찾기
        for(int i = n+1; i >= 0; i--){
            for(int j = n+1; j >= 0; j--){
                // 우측부터 <- 방향으로 탐색
                if (arr[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    isComplete = false;
                    break;
                }
            }
        }

        for(int i = n+1; i >= 0; i--){
            for(int j = n+1; j >= 0; j--){
                // 우측부터 위 방향으로 탐색
                if (arr[j][i] == 1 && !visited[j][i]) {
                    visited[j][i] = true;
                    isComplete = false;
                    break;
                }
            }
        }

        if(!isComplete){
            cnt++;
            int tmp = 0;
            for(int i =0; i <= n+1; i++){
                for(int j = 0; j <= n+1; j++){
                    if(visited[i][j]){
                        arr[i][j] = 0;
                        visited[i][j] = false;
                        tmp++;
                    }
                }
            }
            past = tmp;
        }
    }

    cout << cnt << '\n' << past;

}

 

• 풀이

 

바깥면은 모두 치즈가 아닌 0인 상태!

0,0부터 전체 배열을 dfs/bfs 해가면서 1을 만나면 break 하는 방식으로 외곽 치즈를 구할 수 있다

break 하기 전에 찾은 1의 위치를 넣어두고 

그걸 한번에 수행하면서 몇번이나 하는지 기록하는 방식으로 돌아간다

 

dfs하면서 1 만나면 해당 칸은 더 이상 탐색하지 않고 리턴하고

아니면 계속 주변 칸으로 퍼져나가면서 탐색한다

void dfs(int y, int x) {
    visited[y][x] = true;

    if (arr[y][x] == 1) {
        v.push_back({y, x});
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + pos[i][0];
        int nx = x + pos[i][1];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (visited[ny][nx]) continue;
        dfs(ny, nx);
    }
    return;
}

 

- bfs로 탐색하는 버전, 거의 비슷하다

void bfs(int y, int x) {
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x] = true;

    while (!q.empty()) {
        auto tmp = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = tmp.first + pos[i][0];
            int nx = tmp.second + pos[i][1];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (visited[ny][nx]) continue;

            if (arr[ny][nx] == 1) {
                visited[ny][nx] = true;
                v.push_back({ny, nx});
            } else {
                visited[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    }
}

 

dfs를 호출할때마다 외곽 치즈를 녹이는 작업을 하고 횟수나 한번에 몇개나 녹았는지를 세기 위해서 solution 메서드를 작성했다

dfs를 호출할때마다 visited 배열과 녹은 치즈 위치를 저장해둘 v 배열을 초기화해줘야한다

모든 칸이 0이 될때까지 반복하기 위해 무한루프 구문과 탈출 플래그를 이용했다

void solution() {
    while (true) {
        visited.clear();
        visited.resize(n, vector<bool>(m, false));
        v.clear();
        dfs(0, 0);

        //dfs를 돌면서 찾은 외곽 1을 0으로 바꿔준다
        for (auto tmp: v) {
            arr[tmp.first][tmp.second] = 0;
        }
        // 외곽 크기로 직전에 녹은 치즈 값을 업데이트
        past = v.size();

        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) flag = true;
            }
        }

        cnt++;
        if (!flag) break;
    }
}

 

• 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

int n, m, past = 0, cnt = 0;
vector<vector<int>> arr;
vector<vector<bool>> visited;
vector<pair<int, int>> v;
bool isClear = false;

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

void dfs(int y, int x) {
    visited[y][x] = true;

    if (arr[y][x] == 1) {
        v.push_back({y, x});
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + pos[i][0];
        int nx = x + pos[i][1];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (visited[ny][nx]) continue;
        dfs(ny, nx);
    }
    return;
}

void solution() {
    while (true) {
        visited.clear();
        visited.resize(n, vector<bool>(m, false));
        v.clear();
        dfs(0, 0);

        //dfs를 돌면서 찾은 외곽 1을 0으로 바꿔준다
        for (auto tmp: v) {
            arr[tmp.first][tmp.second] = 0;
        }
        // 외곽 크기로 직전에 녹은 치즈 값을 업데이트
        past = v.size();


        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) flag = true;
            }
        }

        cnt++;
        if (!flag) break;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    arr.resize(n, vector<int>(m));

    for (int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }

    solution();
    cout << cnt << '\n' << past;
}