[알고리즘] 백준 2636번 - 치즈

문제

위에 나와있다시피 쉽게 설명하면 판 위에 놓인 치즈가 몇 시간 뒤에 녹고, 녹기 직전에 몇 칸의 치즈가 남아있는지 구하는 문제이다.

주요 로직

우선, 필요하다고 생각되는 로직은

1. 시간 단위로 변하는 공기와 닿아있는 부분 구하기
2. 구멍 판별하기

위 두 개가 필수적으로 구현해야하는 문제 지점이라고 생각했다.

구멍은 위에 예시 그림으로부터 알 수 있듯이 치즈로만 둘러쌓인 빈 공간을 의미한다.

<그림 1>에서 <그림 2>로 넘어갈 때, 구멍이 공기와 맞닿는 순간 기존에 구멍과 맞닿아 있던 부분의 치즈도 녹기 시작하는 것을 볼 수 있다.

구현

위와 같은 로직들을 구현하기 위해, 우선 구멍을 판별하는 findHoles 함수부터 만들어 보았다.

int N, M, cnt, hole_cnt, answer, iter;

int maps[104][104], visited[104][104], holes[104][104], checked[104][104];

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

void findHoles(int y, int x) {
  for (int i = 0; i < 4; i++) {
    int ny = y + dy[i];
    int nx = x + dx[i];

    if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;

    if (maps[ny][nx]) {
      checked[ny][nx] = 1;
      continue;
    }
    if (visited[ny][nx]) continue;

    if (!visited[ny][nx] && maps[ny][nx] == 0) {
      visited[ny][nx] = 1;
      holes[ny][nx] = 1;
      findHoles(ny, nx);
    }
  }
}

공기는 대각선으로 침투를 못하는 것을 보니 위 문제는 상하좌우 네 방향만을 고려한다.

그렇기 때문에 dy, dx 를 위와 같이 설정해주었고 각각 상, 우, 하, 좌를 나타낸다.

본격적으로 findHoles 함수를 살펴보면, 입력값으로 좌표가 주어지고 해당 좌표에서 움직일 수 있는 좌표를 탐색해야 한다.

if문으로 탐색하는 좌표가 적절한 위치(0이상 가로, 세로 미만)에 있는지 확인해주고 모든 조건을 통과한다면 holes에 해당 좌표의 값을 1로 설정한다.

1로 만들어주는 이유는 시작 좌표에서부터 maps를 순회하면서 닿지 못하는 곳이 있으면 그 곳이 바로 구멍일 것이기 때문이다. 쉽게 말하자면 구멍은 외부와 차단되어 있는 점을 이용하여 위와 같은 함수를 만들었다.

그렇다면 findHoles의 시작 좌표를 어떻게 설정해야할까?

이 부분에 대한 고민을 덜어준 것이 바로 출제자의 배려라고 생각한다.

땡쓰 투 출제자

문제를 보면 알겠지만 판의 가장자리에는 치즈가 위치할 수 없다. 즉, 가장자리에 해당하는 좌표 아무거나 findHoles에 인자로 전달하게 되면 외부 공기에 해당하지 않는 빈 공간에 대한 정보만이 holes배열에 0으로 남게 되는 것이다.

이제 main 코드를 살펴보면,

int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> maps[i][j];
      if (maps[i][j]) {
        holes[i][j] = 1;
        cnt++;
      }
    }
  }

  while (true) {
    memset(visited, 0, sizeof(visited));
    memset(holes, 0, sizeof(holes));
    findHoles(0, 0);
    if (!cnt) break;
    answer = cnt;
    cnt = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (holes[i][j] && !visited[i][j] && !maps[i][j]) {
          dfs(i, j);
        }
      }
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (checked[i][j]) {
          maps[i][j] = 0;
        }
      }
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (maps[i][j]) cnt++;
      }
    }
    iter++;
  }
  cout << iter << "\n" << answer << "\n";
}

입력값을 받음과 동시에 치즈인 경우는 바로 구멍이 아닐 수 밖에 없기 때문에 holes에 1을 넣어주는 것을 확인할 수 있다.

구멍의 위치를 파악한 후, 바로 dfs를 통해 공기와 맞닿아있는 부분을 파악한다.

문제에서 c로 표시된 부분인데, 이 부분 같은 경우는 findHoles에서 check배열에 해당 인덱스를 넣어준다.

그리고 아래 반복문에서 check된 부분을 0으로 만들어 주는 것을 cnt가 0이될 때까지 반복한다.

다행히 정답은 맞았지만 수많은 조건문들과 반복되는 로직의 두 함수(findHoles, dfs)가 뭔가 마음에 들지 않았다.

리팩토링

리팩토링된 부분 중 큰 변화가 이루어진 부분 한 곳만 다뤄보면..!

void dfs(int y, int x) {
  visited[y][x] = 1;
  if (maps[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 || nx < 0 || ny >= N || nx >= M) continue;

    if (visited[ny][nx]) continue;

    dfs(ny, nx);
  }
  return;
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> maps[i][j];
    }
  }

  while (true) {
    memset(visited, 0, sizeof(visited));
    v.clear();
    dfs(0, 0);
    cnt = v.size();
    for (pair<int, int> p : v) {
      maps[p.first][p.second] = 0;
    }
    bool flag = 0;
    ...

공기와 맞닿는 부분에 해당하는 좌표를 vector에 저장한 후에 0으로 바꿔주는 방법이다.

사실 공기에 맞닿는 부분을 찾자마자 return해주면 구멍을 찾을 이유가 자연스레 사라지는 것이다.

약간의 센스가 필요했지만, 뭔가 실전에서는 무식하게 들이받는 것도 필요하다는 생각이 들기도 했다.