2636 : 치즈 - DFS, BFS

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

2636번: 치즈

문제요약

공기와 접촉한 치즈의 표면이 녹아내릴 때, 모두 녹는 데 걸리는 시간과 녹기 1시간 전의 크기.

 

난이도

Gold 4

---

풀이 포인트

 

• 어떤 것을 중심으로 dfs를 돌릴지 잘 생각해야함.

---

REVIEW

 

내가 하고 싶었던 건, 이동 방향에 우선순위를 두어

치즈 덩이(연결요소)의 시작점으로부터 반 시계방향 (아래,오른쪽,위, 왼쪽으로) 탐색하며 가장자리를 칠해가는 방식이었다.

풀이가 복잡해지는데 느낀 순간 오답이겠거니 했다.

어찌저찌 테스트케이스는 통과했는데 왜 틀린 건지는 일단 분석중이다.

 

모범 풀이에서는 여백에서부터 dfs를 돌려 1을 만난 순간, 치즈와 접촉한 순간, 그 좌표를 저장한다.

치즈에서 부터 가장자리를 생각하면 내부 공백 등을 처리하기가 굉장히 복잡해지는데,

여백에서부터 가장자리를 찾아나가면 dfs 돌리기가 아주 수월하다..

 

항상 경우의 수가 너무 많아진다고 생각할 땐 여집합을 생각하자..!

여집합 vs 지금 구하는 경우의 수 의 크기를 가늠해서 전체에서 여집합을 빼준다는 생각.

항상 반전시켜보려는 아이디어 습득하기. 

---

CODE

#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;
    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;
        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();
        go(0, 0);
        cnt2 = v.size();
        for (pair<int, int> b : v)
        {
            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;
            }
        }
        cnt++;
        if (!flag)
            break;
    }
    cout << cnt << '\n'
         << cnt2 << '\n';
}