[백준 / BOJ] C++ 2638 치즈

2638번: 치즈

 

문제

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

2638번: 치즈

 

 

풀이

공기에 두 면이 접촉해 있는 치즈는 사라진다. 발상이 중요한 문제로 치즈를 기준으로 탐색할지, 공기를 기준으로 탐색할지 기준을 잘 세워야 하는 문제다. 

 

정답 풀이

이 문제에서 같은 시간에 사라지는 치즈가 모두 사라진 뒤 동시에 공기가 침투한다. 따라서 치즈가 사라지는 로직과 공기가 퍼지는 로직이 턴제로 진행되야 한다.

 

중요! 모눈종이의 맨 가장자리는 치즈가 놓이지 않는 것으로 가정한다. 따라서 모든 공기는 반드시 이어져 있으므로  (0, 0)에서 BFS를 통해 공기가 통하는 부분을 먼저 판단해줘야 한다. 그런 다음 N과 M의 크기가 최대 100밖에 되지 않으므로 이중 for문으로 완전 탐색 해주면 된다. {i, j}에 대해 graph[i][j] = 1 일 때, 상하좌우로 공기의 수를 세고 공기가 두 면 이상 접촉해 있다면 벡터에 좌표를 보관해 둔다. 모두 탐색했다면 벡터에 있던 모든 구멍이 난 위치에 대해 BFS를 한다. 공기가 그곳을 통해 안으로 침투할 수도 있기 때문. 그런 다음 또다시 모든 좌표에 대해 탐색하는 과정을 반복한다.

 

여기서 탐색을 더 이상 남은 치즈가 없으면 탐색을 멈춰야 한다. 따라서 치즈가 상하좌우를 탐색했는데 공기가 두 면 이상 접촉해 있지 않다면 아직 사라질 치즈가 남은 것이므로 탐색을 반복하도록 flag를 세웠다.

 

 

오답 풀이

아래 모든 오답은 결국 "공기가 침투하는 상황"을 고려하지 않았었다..  추가로 "가장자리에는 치즈가 놓이지 않는다"는 것도..

처음 접근 방식은 치즈를 기준으로 탐색했다. 치즈를 기준으로 탐색하면 불필요한 탐색을 하지 않아도 될 것이라 생각했기 때문인데 치즈가 사라지면 바로 해당 위치를 공기로 바꿨었다. 그러나 치즈가 맞닿아 있는 경우 사라지지 않아야할 치즈들이 사라졌다.

 

그다음으로 바꾼 것은 방문처리였다. 방문한 시간을 기록해 현재 시간보다 전에 방문한 위치의 수만 세도록 했다. 그러면 동시에 사라진 치즈를 세지 않도록 할 수 있었다. 접근법은 나쁘지 않았던 것 같지만 문제를 꼼꼼히 읽는 습관을 길러야 할 필요성을 느꼈다..

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, t = 0, graph[100][100], visited[100][100];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void bfs(int xx, int yy) {
  queue<pair<int, int>> q;
  visited[xx][yy] = 1;
  q.push({xx, yy});
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    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 (!visited[nx][ny] && graph[nx][ny] == 0) {
        visited[nx][ny] = 1;
        q.push({nx, ny});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      cin >> graph[i][j];
      visited[i][j] = 0;
    }
  bfs(0, 0);
  while (1) {
    t++;
    vector<pair<int, int>> hole;
    bool flag = true;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (graph[i][j] == 1)
          if (!visited[i][j]) {
            int cnt = 0;
            for (int a = 0; a < 4; a++) {
              int x = i + dx[a];
              int y = j + dy[a];
              if (visited[x][y])
                cnt++;
            }
            if (cnt >= 2)
              hole.push_back({i, j});
            else
              flag = false;
          }
    for (auto p : hole) {
      int x = p.first;
      int y = p.second;
      bfs(x, y);
    }
    if (flag)
      break;
  }
  cout << t;
  return 0;
}