2667번: 단지번호붙이기

네르기·2022년 11월 17일
DFS백트래킹
0

알고리즘

목록 보기
75/76

어떤 문제인가?

DFS를 이용하여 전체 탐색을 하는 문제.

시행착오 횟수

잘못된 구상으로 1번 헤맸고, 3번 틀렸음.

1차 시도

처음 표를 보고, 다음과 같은 생각이 들었다.

이걸 인접 행렬로 생각해보는 건 어떨까?

그래서 다음과 같은 4×44 \times 4 행렬을 가지고 그래프를 그려보았다.

[1011000110111000]\begin{bmatrix} 1 && 0 && 1 && 1 \\ 0 && 0 && 0 && 1 \\ 1 && 0 && 1 && 1 \\ 1 && 0 && 0 && 0 \end{bmatrix}

그런데 이렇게 되면, 2번을 제외하고 나머지 지점을 고르면 모든 지점을 전부 방문하게 되어버리므로 정확한 답을 얻을 수가 없다.
그래서 한 발짝 물러나서 이렇게 접근해보기로 했다.

모든 지점을 전부 방문하긴 방문해야 하니, 네 방향을 전부 들르는 DFS 탐색을 구현해보자.

1차 시도, 1차 수정

위 생각을 바탕으로 짠 첫 코드다.

#include <stdio.h>

int table[25][25];
int visited[25][25];
int count[25][25];
int N = 0;

int visit(int x, int y, int count) {
  if (table[x][y] == 0)
    return count;
  if (x < N - 1 && table[x + 1][y] != 0 && visited[x + 1][y] != 1) {
    visited[x + 1][y] = 1;
    count += visit(x + 1, y, 1);
  }
  if (x > 1 && table[x - 1][y] != 0 && visited[x - 1][y] != 1) {
    visited[x - 1][y] = 1;
    count += visit(x - 1, y, 1);
  }
  if (y < N - 1 && table[x][y + 1] != 0 && visited[x][y + 1] != 1) {
    visited[x][y + 1] = 1;
    count += visit(x, y + 1, 1);
  }
  if (y > 1 && table[x][y - 1] != 0 && visited[x][y - 1] != 1) {
    visited[x][y - 1] = 1;
    count += visit(x, y - 1, 1);
  }
  return count + 1;
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      char input = getchar();
      if (input == '0')
        table[i][j] = 1;
      else if (input == '1')
        table[i][j] = 0;
    }
    getchar();
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      int count = visit(x, y, 0);
      printf("%d\n", count);
    }
  }
  return 0;
}

이 코드에는 치명적인 문제가 있었다. 이는 다음 문단에서 후술하겠다.
문제가 있었던만큼 당연히 작동하지 않았고, 이 때 시간이 없어서 푸는 것을 잠시 미뤘었다.

1차 시도, 2차 수정

#include <stdio.h>

int table[25][25];
int visited[25][25];
int N = 0;

int dfs(int x, int y, int count) {
  if (x < 0 || x > N || y < 0 || y > N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return count;
  printf("(%d,%d) : %d\n", x, y, count);
  visited[x][y] = 1;
  return dfs(x - 1, y, count + 1) + dfs(x + 1, y, count + 1) +
         dfs(x, y - 1, count + 1) + dfs(x, y + 1, count + 1);
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      char input = getchar();
      if (input == '0')
        table[i][j] = 1;
      else if (input == '1')
        table[i][j] = 0;
    }
    getchar();
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      int count = dfs(x, y, 0);
      printf("%d\n", count);
    }
  }
  return 0;
}

dfs() 코드를 조금 다듬어서, 4방향으로 각각 탐색할 때 인접한 타일 개수를 더한 값을 반환하도록 했다.
이미 방문한 곳이라면 집계가 되지 않고 멈출 것이므로, 원리 자체만 두고 보면 괜찮았지만, 문제는 이전 갯수를 그대로 활용한 점이었다.

count + 1이 들어간 결과, 결국 count가 늘어났든 말든 각 재귀마다 4씩 더해지게 되어 이 또한 제대로 된 결과를 내지 못한다. 따라서 이 코드를 또 다시 고칠 필요가 있었다.

1차 시도, 3차 수정

#include <stdio.h>

int table[25][25];
int visited[25][25];
int N = 0;

int dfs(int x, int y, int count) {
  if (x < 0 || x > N || y < 0 || y > N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return count;
  printf("(%d,%d) : %d\n", x, y, count);
  visited[x][y] = 1;
  return dfs(x - 1, y, count + 1) + dfs(x + 1, y, count + 1) +
         dfs(x, y - 1, count + 1) + dfs(x, y + 1, count + 1);
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      char input = getchar();
      if (input == '0')
        table[i][j] = 0;
      else if (input == '1')
        table[i][j] = 1;
    }
    getchar();
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      int count = dfs(x, y, 0);
      printf("%d\n", count);
    }
  }
  return 0;
}

앞서 말했던 '치명적 실수'가 뭔지 알아차렸는가? 멍청하게도 '0' 일때 1을 넣었고 '1' 일때 0을 넣었다. 이 부분을 고쳤다.

1차 시도, 4차 수정

#include <stdio.h>

int table[25][25];
int visited[25][25];
int N = 0;

int dfs(int x, int y, int count) {
  if (x < 0 || x > N || y < 0 || y > N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return count;
  printf("(%d,%d) : %d\n", x, y, count);
  visited[x][y] = 1;
  return dfs(x - 1, y, count + 1) + dfs(x + 1, y, count + 1) +
         dfs(x, y - 1, count + 1) + dfs(x, y + 1, count + 1);
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%1d", &table[i][j]);
    }
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      int count = dfs(x, y, 0);
      printf("%d\n", count);
    }
  }
  return 0;
}

getchar() 로 입력받는 부분에서 뭔가 찜찜한 느낌이 들어 printf 함수로 제대로 입력을 받았는지 확인했는데, 역시나 제대로 받지 못하고 있었다. 시중에 있는 답안을 참고한 결과 scanf("%1d")를 이용하면 딱 한 문자만 받을 수 있다는 걸 알게 되어 바로 적용했다.

1차 시도, 5차 수정: WA

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) a > b ? a : b

int table[25][25];
int visited[25][25];
int count[313];

int N = 0;
int apartCount = 0;

int compare(const void *a, const void *b) {
  if (*(int *)a > *(int *)b)
    return 1;
  else if (*(int *)a < *(int *)b)
    return -1;
  else
    return 0;
}

int dfs(int x, int y, int count) {
  if (x < 0 || x > N || y < 0 || y > N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return count;

  visited[x][y] = 1;
  count++;
  count = MAX(count, dfs(x + 1, y, count));
  count = MAX(count, dfs(x - 1, y, count));
  count = MAX(count, dfs(x, y - 1, count));
  count = MAX(count, dfs(x, y + 1, count));
  return count;
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%1d", &table[i][j]);
    }
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      int c = dfs(x, y, 0);
      printf("c=%d\n", c);
      if (c > 0)
        count[apartCount++] = c;
    }
  }

  qsort(count, apartCount, sizeof(int), compare);
  printf("%d\n", apartCount);
  for (int i = 0; i < apartCount; i++) {
    printf("%d\n", count[i]);
  }

  return 0;
}

4차 수정까지는 완전한 코드가 아니었다. 정렬하는 부분도 빠져 있고, 총 단지 개수를 구하는 부분도 빠져 있었다.
기존에 더하는 부분을, count라는 매개변수의 원래 값과 dfs()의 값의 최대값을 비교하는 부분으로 바꿨다. 만약에 인접한 아파트 단지가 있다면 dfs() 값은 항상 count보다 클 것이므로, 최댓값을 이용한 대입이 먹힐 것으로 생각했다.

그런데, 이게 맞기를 바랬지만 '틀렸습니다'를 받았다. 무엇이 잘못되었는지를 한번 살펴보자.

2차 시도: WA

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) a > b ? a : b

int table[25][25];
int visited[25][25];
int count[315];
int maxCount = 0;

int N = 0;
int apartCount = 0;

int compare(const void *a, const void *b) {
  if (*(int *)a > *(int *)b)
    return 1;
  else if (*(int *)a < *(int *)b)
    return -1;
  else
    return 0;
}

void dfs(int x, int y) {
  if (x < 0 || x > N || y < 0 || y > N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return;

  visited[x][y] = 1;
  maxCount++;
  dfs(x + 1, y);
  dfs(x - 1, y);
  dfs(x, y - 1);
  dfs(x, y + 1);
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%1d", &table[i][j]);
    }
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      maxCount = 0;
      dfs(x, y);
      if (maxCount > 0)
        count[apartCount++] = maxCount;
    }
  }

  qsort(count, apartCount, sizeof(int), compare);
  printf("%d\n", apartCount);
  for (int i = 0; i < apartCount; i++) {
    printf("%d\n", count[i]);
  }

  return 0;
}

gdb까지 동원하여 count의 변화를 살펴보았는데, 이상하게도 dfs()의 값이 count보다 더 커서 대입될 것이라 생각했던 부분에서 count의 값이 계속해서 대신 대입됐다. 최댓값 자체는 정확하게 구하는데, 재귀로 타고 내려갔던 길을 다시 올라가는 과정에서 문제가 발생한 듯 싶었다.

이 부분을 하루 종일 붙잡기에는 내 인내심이 조금씩 바닥나고 있었기 때문에, 전역변수로 따로 빼둔 다음 dfs() 호출 전에 0으로 초기화시켰다. 이래놓고 나니 전형적인 백트래킹 문제가 되어버렸다.

그런데 이 코드 또한 내 발목을 잡았다. 도대체 무엇이 문제였던 것일까?

3차 시도: AC

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) a > b ? a : b

int table[25][25];
int visited[25][25];
int count[315];
int maxCount = 0;

int N = 0;
int apartCount = 0;

int compare(const void *a, const void *b) {
  if (*(int *)a > *(int *)b)
    return 1;
  else if (*(int *)a < *(int *)b)
    return -1;
  else
    return 0;
}

void dfs(int x, int y) {
  if (x < 0 || x >= N || y < 0 || y >= N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return;

  visited[x][y] = 1;
  maxCount++;
  dfs(x + 1, y);
  dfs(x - 1, y);
  dfs(x, y - 1);
  dfs(x, y + 1);
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%1d", &table[i][j]);
    }
  }

  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
      maxCount = 0;
      dfs(x, y);
      if (maxCount > 0)
        count[apartCount++] = maxCount;
    }
  }

  qsort(count, apartCount, sizeof(int), compare);
  printf("%d\n", apartCount);
  for (int i = 0; i < apartCount; i++) {
    printf("%d\n", count[i]);
  }

  return 0;
}

그랬다. x > N || y > N이 아니라 x >= N || y >= N이었던 것이다!
전자의 경우에는 N = 4일 때 x = 4인 경우까지 고려하므로 틀릴 수가 있었다. 이런! 경계 조건을 잘못 본 탓에 거의 다 맞은 문제를 틀려버렸다.

문제에서 배운 것들

  1. scanf()의 또다른 활용법
    -> 문자를 NN개씩 받고 싶다면, 서식문자 %Nd을 이용하자(ex. %1d).
  2. 매개변수에 직접 대입하는 방식은 피하자
    -> 이유를 정확하게 파악하진 못했으나, 이 문제로 30분가량 뒹굴었으면 깨달을 때도 됐다.
profile
네르기
프로그래머와 애니메이터가 되고파
이전 포스트

1260: DFS와 BFS

다음 포스트

1012: 유기농 배추

0개의 댓글