Intuition

문제에 기술되어 있는 대로 구현만 하면 된다.
특별한 알고리즘이 필요하지 않았다.

Approach

좌표 처리

네 방향의 좌표들을 편리하게 처리하기 위해 아래 같은 방식을 사용했다.

  int dr[4] = {-1, 0, 1, 0};
  int dc[4] = {0, 1, 0, -1};
  ...
  for (int i = 0; i < 4; i++) {
    if (room[r + dr[i]][c + dc[i]] == 0)
      ...
  }
  if (...) {
    for (int i = 0; i < 4; i++) {
      d = (d + 3) % 4;
      if (room[r + dr[d]][c + dc[d]] == 0) {
        clean(r + dr[d], c + dc[d]);

테두리

이런 배열을 활용하는 문제는 항상 테두리에 주의해야 한다.
배열의 크기를 넘어가지는 않는지, 인덱스가 0이 되지는 않는지 말이다.
그러나 이번 문제 같은 경우는 항상 동서남북으로 벽이 있다. 그리고 이 벽을 코드 구조상 접근하지 않기 때문에, 따로 범위를 체크할 필요는 없다.

Solution

#include <stdio.h>

int room[50][50];
int cnt;
int n, m;
int d;
void clean(int r, int c);

int main(void) {
  scanf("%d %d", &n, &m);
  int r, c;
  scanf("%d %d %d", &r, &c, &d);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &room[i][j]);
    }
  }
  clean(r, c);
  printf("%d\n", cnt);
}

void clean(int r, int c) {
  // printf("%d %d\n", r, c);
  if (room[r][c] != 2) {
    room[r][c] = 2;
    cnt++;
  }
  int dr[4] = {-1, 0, 1, 0};
  int dc[4] = {0, 1, 0, -1};
  int status = 0;
  for (int i = 0; i < 4; i++) {
    if (room[r + dr[i]][c + dc[i]] == 0)
      status = 1;
  }
  if (status) {
    for (int i = 0; i < 4; i++) {
      d = (d + 3) % 4;
      if (room[r + dr[d]][c + dc[d]] == 0) {
        clean(r + dr[d], c + dc[d]);
        break;
      }
    }
  } else {
    // printf("%d\n", d);
    int d_back = (d + 2) % 4;
    if (room[r + dr[d_back]][c + dc[d_back]] != 1)
      clean(r + dr[d_back], c + dc[d_back]);
  }
}

Time Complexity

정확하게 계산하지 못해서 rough하게만 생각해봤다.
후진하는 케이스로 인해 이미 방문한 곳을 또 방문하지만, 그래봤자 $2N^2$일 것이라 추정했다.
$O(N^2)$

지적 및 질문 환영