[백준 24727] 인지융~ [Java]

문제

http://boj.ma/24727

요약

• N * N 배열에 C, E개의 공간을 서로 인접하지 않도록 배치하자.
• 만약 배치할 수 없다면 - 1을 출력하자.

---

풀이 과정

아이디어

두 종류의 공간을 최대한 겹치지 않게 배치하기 위해서는, 각 공간에 인접하는 빈 영역이 최소가 되도록 배치해야 한다.

좀 더 구체적으로는 아래와 같이 규칙을 세울 수 있다.

• 배열의 경계선에 최대한 붙이며
• 인접한 빈 영역의 수를 최소화

따라서 각 공간은 밀집되어야 하지만, 공간 간에는 최대한 배척해야 한다.

수평/수직 구조 보다, 계단형식으로 공간을 구성하는 것이 합리적이다.

1. 임의의 모서리를 정하고
2. 중앙을 향한 가상의 선분에 수직 방향으로 배치하면 된다.
3. 나머지 영역은 마주보는 방향의 모서리에서
4. 반대 방향으로 배치하면 된다.

그림으로 나타내면 아래와 같다.

private static boolean solve(int C, int E) {
  if (N * N <= C + E) {
    return false;
  }
  fillA(C);
  return fillB(E);
}

private static void fillA(int cnt) {
  for (int i = 0; i < 2*N; ++i) {
    for (int j = 0; j <= i; ++j) {
      int r = i - j;
      if (r >= N || j >= N) {
        continue;
      }
      board[r][j] = 1;
      if (--cnt == 0) {
        return;
      }
    }
  }
}

private static boolean fillB(int cnt) {
  for (int i = N - 1; i >= -N; --i) {
    for (int j = N - 1; j >= i; --j) {
      int r = i + (N - j - 1);
        if (r < 0 || j < 0) {
          continue;
        }
        if (board[r][j] == 1 ||
            (j > 0 && board[r][j - 1] == 1) ||
            (r > 0 && board[r - 1][j] == 1)) {
          return false;
        }

        board[r][j] = 2;
        if (--cnt == 0) return true;
      }
  }
  return false;
}

구현의 단순함을 위해 탐색 범위는 $2N^2$ 으로 하고, 유효한 범위에서만 배치하도록 구현했다.

만약 B를 채우다가. 인접한 영역에 A가 있다면 유효한 배치가 존재하지 않은 경우로, -1을 출력하면 된다.

성능 분석

• 시간 복잡도: $O(N^2)$
• 제출결과: Accepted / 108ms / 14,388KB

---

회고

계단 형식으로 영역을 배치하는 로직을 구현하는 과정에서, 습관적으로 탐색 범위를 N으로 제한한 채 구현해 일부 영역이 끝까지 배치되지 않는 오류가 발생했다.

이 문제는 실제로도 원인을 파악하는 데 상당한 시간이 걸렸고, 풀이 글을 작성하며 다른 사람이 이해할 수 있도록 구조를 정리하고 시각 자료를 만들던 과정에서 놓치고 있던 조건을 발견할 수 있었다.

결과적으로 설명하는 과정 자체가 디버깅의 역할을 했고, 혼자서만 코드를 들여다볼 때보다 사고의 맹점을 더 빠르게 드러내 주었다.

앞으로도 문제를 풀다가 원인을 쉽게 찾기 어려운 경우, 해결 과정을 스스로에게 설명하며 다시 검증하는 습관을 유지해야겠다고 느꼈다.

---

참고

문제

http://boj.ma/24727

24727번: 인지융~

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/24727.java

problem-solving/baekjoon-online-judge/normal/24727.java at main · rogi-rogi/problem-solving