Last updated on

백준 2288번: 격자의 분리자

해답 코드 전문을 올려놓지 않으니 참고 바랍니다.

2288번: 격자의 분리자

문제 설명

N x M 격자 공간을 왼쪽(White) 구역과 오른쪽(Black) 구역으로 분리하고자 한다. 이를 위해 격자 내의 칸들을 적절히 선택하여 왼쪽 구역과 오른쪽 구역 어느 곳에도 소속되지 않는 일종의 ‘중립 지대’를 형성할 것인데, 이 구역을 분리자(Separator)라고 칭한다.

즉, 격자 안의 칸은 각각 왼쪽 구역, 오른쪽 구역, 분리자 중 하나에 소속된다. 편의상 각 칸을 W, B, S로 표시한다.

본 문제는 분리자에 의해 두 영역이 분리된 격자가 주어졌을 때, 정해진 방법으로 분리자의 구역을 바꾸어서 분리자가 차지하는 영역을 최소로 하는 방법을 찾는 문제이다. 단, 그 때의 분리자의 형태를 출력할 필요는 없고 최소로 했을 때 그 분리자의 넓이만을 출력하면 충분하다.

분리자의 조건

이 문제의 난도에 가장 큰 비중을 차지하는 것은 지문의 난해함이다. 이를 좀 정리해보겠다. 분리자가 만족해야 하는 조건을 예시와 함께 설명하겠다.

유효한 파티션 조건

  • Separator (분리자) : W와 B는 대각선을 포함한 8방향 모두에서 절대로 인접할 수 없다. 위 그림 두 번째 예시에서는 붉은 색 테두리끼리 인접하여 조건을 위반한다.
  • Corner (꼭짓점) : 꼭짓점에는 S가 들어갈 수 없다.
  • Minimal (최소성) : S가 어떤 칸이든 제거된다면 더 이상 분리자로 기능할 수 없다. 다시말해, 분리자는 가능한 한 최소한의 공간만을 차지해야 한다. 위 그림 네 번째 예시에서는 붉은 색 테두리으로 표시된 칸 중 하나를 제거해도 여전히 구역이 분리가 되기 때문에 유효한 분리자가 아니다.

다음 두 조건은 위 조건들과 비교했을 때 조금 독특한 조건이다. 기존 조건들은 분리자를 칸들의 집합, 즉 ‘구역’으로 취급하였다. 그러나 아래의 두 조건은 분리자를 시작점과 끝점을 잇는 ‘이동 경로’처럼 다룬다.

  • Top-to-Bottom : 분리자는 첫번째 줄에서 시작해서 마지막 줄에서 끝나야 한다. 즉, 1번째 줄과 N번째 줄에 S가 하나는 포함되어야 한다. 위 다섯번째 예시에서는 첫 줄에 S가 없어서 조건이 위배된다.
  • Never go up : 분리자 공간을 위에서 아래로 따라갈 때, 위쪽 방향으로는 이동해선 안된다. 이에 관한 예시는 아래 그림에서 확인할 수 있다.

분리자 조건 2

올바르게 분리자를 만들려면, 첫번째 줄에서 시작해서, 왼쪽, 오른쪽, 아래쪽 방향으로만 이동해서, 마지막 줄에 도착해야 한다. 위쪽으로 이동은 못하니 1번째 줄에서 N번째 줄까지 도달하는 과정에서 아래쪽 이동은 정확히 N-1번 발생한다. 곧, 분리자는 아래쪽으로 N-1번 이동하는 중간중간에, 원하는 만큼 왼쪽과 오른쪽으로 왔다갔다하는 과정으로 형성된다. 위 그림의 두 번째, 세 번째 예시는 그 과정을 화살표로 보여주고 있다.

올바르게 형성된 분리자는 격자의 각 행(row)이 연속된 세 구간으로 나뉜다. 무슨 뜻이냐면, 첫 번째 예제의 세 번째 줄을 보면 WSBBSSSB로, 연속된 구간이 W-S-BB-SSS-B 총 5개가 형성된다. 반면, Never go up 조건이 준수된 두 번째 예제의 경우 모든 행(row)이 연속된 W, 연속된 S, 연속된 B의 세 구간으로 깔끔하게 떨어진다.

한편, 한 행이 세 개 미만의 구간으로 구성되는 경우도 있을까? 다시말해 연속된 W나 연속된 B 같은 것이 하나도 존재하지 않는 경우가 있을까? Top-to-bottom 조건에 의해 각 행에 S가 하나씩은 포함되어야 한다는 점은 자명하다. 하지만 위 예시 세번째의 경우 두 번째 행에는 W가, 세 번째 행에는 B가 누락되어 있다.

해당 예시는 올바른 분리자가 아니다. 그러나 Never go up, Top-to-bottom 조건을 위반하지 않았다. 정의에 따르면 S는 공간을 분리하여 W와 B라는 두 개의 “연결 요소(connected component)“를 만든다고 한다. 다만 해당 예시에서는 W끼리, B끼리 완전히 연결되지 못한 상태이다. 구역이 올바르게 연결되려면 각 행마다 최소 1개씩의 W와 B가 필요하다. 영문 번역에서는 이를 입력 명세에서 명시적으로 보장하고 있다.

It is confirmed that each of these three characters appears at least once in each line.

분리자의 변경

문제의 입력에서 이미 (유효한) 분리자의 형태는 주어진다. 다만, 크기가 최소인 분리자를 만들기 위해 다음 두 가지의 변경이 허용된다.

  1. S 바로 오른쪽 B를, S로 변경
  2. S를 W로 변경

두 액션을 한 칸에 동시에 적용하는 것은 불가능하다. 즉, 1번에 따라 B를 S로 바꾼 다음 거기에 2번을 적용해 W로 바꿀 수 없다. 최초에 주어진 입력의 형태에 따라서 다음과 같은 변경이 가능하다.

  • W : W로 고정
  • S : W or S 선택 가능
  • B : 왼쪽에 S가 있었는지에 따라 차이
    • 왼쪽이 S : B or S 선택 가능
    • 왼쪽이 B : B로 고정

이를 시각화하면, 다음과 같은 그림을 그릴 수 있다. 한 칸에 두 개의 색을 표시한 부분은 둘 중 하나를 (올바른 분리자가 형성되는 한) 임의로 선택할 수 있다는 의미이다.

분리자 변경 예시

풀이 방법

본 문제는 S가 놓일 수 있는 잠재적인 공간이 주어진 상태에서, Minimal 분리자의 크기를 구하는 문제로 환원할 수 있다.

1번째 줄에서 N번째 줄로 가는 과정에서의 최단경로를 구하는, O(NM) BFS 문제가 되는 것이다. 출발점/도착점이 각 2개라는 사실, Corner 조건에 대한 예외 처리가 필요하다는 사실 정도를 유의하면 된다.

별해

나는 문제를 풀 때 이 문제가 최단 경로를 구하는 문제임을 자각하지 못했고, 분리자의 특성을 더 관찰하여 문제를 풀었다. 입력을 받을 때 이미 O(NM)이 소요되기 때문에 시간 관점에서 특별히 최적화되지는 않았다. 정형화된 방식이 아닌 애드 혹(Ad-hoc) 풀이를 소개하고자 이 포스트를 작성하게 되었다.

분리자를 제약하는 조건이 상당히 많기 때문에, 분리자의 전체 정보가 주어지지 않더라도 제약을 이용해서 분리자의 나머지 정보를 복구할 수 있을 것이라고 생각했다. 다시 말해, 분리자의 핵심 속성을 뽑아내고자 하였다. 내가 관찰한 것은, 각 행의 가장 오른쪽에 있는 분리자 칸의 위치만 알아낸다면, 온전한 분리자의 모습을 복구할 수 있다는 것이었다.

분리자 복구 방법

구체적인 방법은 다음과 같다. 인접한 두 행의 가장 오른쪽 분리자 칸의 위치를 비교한다. 두 칸이 같은 열에 있다면 별도의 처리가 필요 없다. 다른 열에 있다면, 상대적으로 오른쪽에 있는 분리자 칸에서 시작하여, 두 칸이 연결될 때까지, 분리자를 확장하면 된다.

그렇게 되면 분리자의 크기도 쉽게 계산할 수 있다. i번째 행(1 <= i <= N)의 가장 오른쪽 분리자가 있는 열을 R_i(1 <= R_i <= M)이라 하자. 그러면, 분리자의 크기는 다음과 같이 계산할 수 있다.

|S| = N + sum(i=2..N) |R_i - R_{i-1}|

즉, 분리자의 크기는 x좌표 누적 변화량에 비례한다. (경로 관점으로 해석하면, ‘오른쪽’ 또는 ‘왼쪽’으로 이동하는 횟수와 같다.) 이제 이 값이 작아지도록 R_i의 값을 적절히 변경하는 방법을 고안하면 된다.

단, R_i를 아무렇게나 지정한다고 유효한 분리자가 만들어지는 것은 아니라서, 변경 과정에서 분리자의 조건을 위반하는 지 신경써야 한다. 다행히 문제의 입력에서 한번 유효성이 검증된 분리자가 들어오기 때문에 유효성이 깨지는 경우를 따지는 것이 그렇게 까다롭지는 않다.

문제에서 정의된 변경 행동이 R_i와 어떤 관련을 갖는지 정리하면 다음과 같다.

  • B를 S에 포함시키는 것은 R_i를 오른쪽으로 옮기는 것과 같다. S 바로 오른쪽에만 이 행동이 가능하다는 문제의 제약 조건상 R_i는 최대 1칸만 키울 수 있다.
  • S를 W로 바꾸는 것은, 제거하는 S의 위치에 따라 R_i가 변하지 않거나(왼쪽 S), 줄어든다(오른쪽 S). 줄어드는 것은 min(R_{i-1}, R_{i+1}) 범위 내에서만 허용된다.

R_i 줄이기

하지만 R_i를 줄이는 것은 분리자의 크기를 줄이는 데 전혀 기여하지 못한다. 위 그림을 보면 알 수 있다. R_i를 줄임으로써 i번째 행의 분리자 개수를 줄이는 만큼, R_{i-1}의 분리자 개수를 늘리고 있기 때문이다. R_i를 줄여서 분리자 크기를 줄이기 위해서는 R_{i-1} < R_i > R_{i+1}의 대소관계를 가지고 있어야 한다. 그러나 이러한 경우는 Minimal 조건을 위반하기 때문에 입력으로 주어지지 않는다.

결국 분리자의 크기를 줄일 수 있는 유일한 행동은 R_{i+1}를 한 칸 위로 올리는 것이다. 그러나 같은 논리로, R_{i-1} > R_i < R_{i+1}일때만 분리자의 크기를 2 줄일 수 있다. 이 경우에는 Minimal 조건을 위반하지 않아 이러한 경우를 찾는 대로 적용하는 전략을 생각해볼 수 있다.

인접행 대소비교에 따른 유효성

R_{i-1} > R_i < R_{i+1} 조건이 당장 성립하지 않더라도, 여러 행에 걸쳐서 C자 모양을 형성하고 있으면 ‘C자 모양의 왼쪽 모서리’를 한칸 오른쪽으로 끌어당김으로써 동일한 효과를 얻을 수 있다. 또, C자 모양이 완성되지 않더라도 위쪽 또는 아래쪽 끝에 걸쳐있는 경우에는 분리자의 크기를 1만큼 줄일 수 있다.

C자 모양과 양끝 예외 케이스

이제 다음과 같은 알고리즘을 이용하여 최소 분리자 크기를 계산할 수 있다.

  1. 격자 정보를 읽고, 원래 크기 |S|, 각 행의 가장 오른쪽 분리자 위치 R_i를 계산한다.
  2. R_i의 증감을 관찰했을 때 ‘C자 모양’이 만들어지는 경우, 그때마다 |S|에 2를 뺀다.
  3. 첫 줄부터 시작해서 ‘L자 모양’, 또는 마지막 줄부터 시작하여 ‘Γ자 모양’이 만들어지는 경우, 그때마다 |S|에서 1을 뺀다.
  4. 최소화된 |S|를 출력한다.

‘C자 모양’은 R_i가 i가 증가함에 따라서 “감소한 이후 다시 증가하는 경우”, ‘L자 모양’은 “처음에 감소하지 않은 채로 증가한 경우”, ‘Γ자 모양’은 “감소한 채로 증가하지 않고 끝난 경우” 나타난다.

R_i의 증감이 중요하므로 R_i와 R_{i+1}의 대소관계를 비교하여 <, =, > 중 하나의 기호로 표시하는 방식으로 해석하면 유용하다. 문제에 제시된 예제를 이를 이용하여 표현해보자.

(R_1, ..., R_6) = (3, 3, 2, 2, 4, 4)

그러면 (=, >, =, <, =)이 된다. 여기서 ‘C자 구간’은 (>, =, <)이다. 중간에 =가 없어도 되고 여러 개 있어도 상관없다. ‘L자 구간’은 (=, ..., =, <), 반대로 ‘Γ자 구간은’ (>, =, ..., =)으로 표현될 것이다. 이때 등호 기호는 구간을 판단하는 데 있어 유의미한 기여를 하지 않는 모습을 볼 수 있다.

등호를 제거하면, (>, <)이 된다. 즉, 인접 행 대소를 비교해서 그것이 같지 않을 때만을 기호로 표현하고, (>, <) 구간이 만들어지거나 최초에 <로 시작하거나 마지막에 >로 끝날 때마다 앞서 설명한 알고리즘에 의해 해당 구간내 왼쪽 모서리를 오른쪽으로 한 칸 전진시켜서 2칸 또는 1칸의 분리자를 절약하는 방식을 사용하면, 최적의 분리자를 형성할 수 있다. 다시 말하지만 문제는 최적의 분리자 그 자체 대신 단지 크기만을 요구하고 있으므로 절약되는 칸의 총량을 추적하여 이를 답하면 된다.

후기

이 문제의 풀이를 블로그에 올리기로 결정하게 된 계기는, 지문 자체도 장황했고 내 풀이 또한 전형적인 방법이 아니었던 관계로, 중간중간 ‘이렇게 풀어도 되나’ 찝찝했던 부분을 정리하는 차원에서 였다.

지문과 풀이의 논리를 하나씩 정리하면서 왜 이 문제가 이렇게 복잡해졌는지 그 이유를 알 것 같았다. 그 복잡성은 ‘분리자’라는 일상적인 개념을 수학적으로 엄밀하게 정의하려는 시도에서 시작됐다.

문제에서 ‘정점’, ‘부분집합’과 같이 수학적 용어를 쓰며 겁을 주었던 다양하고 복잡한 제약들은, 격자 공간을 주어준 다음, “이 공간을 왼쪽과 오른쪽 구역으로 분리하세요”라고 사람들에게 시켜봤을 때 예상할 수 있는 상식적인 수준의 것이었다. 분리자의 제약 조건, 분리자의 크기를 줄이는 단계의 정보를 예시(반례)를 통해 상식적인 언어로 풀어내는 것이 중요한 문제였다.

다만 효율적인 분리자를 그리기 위해 ‘BFS로 최단 경로를 그리는 해법’은 상식적인 접근 방법이라기보단 알고리즘적 접근 방법이었다. 문제를 풀기 위해 분리자를 ‘이동 경로’의 개념으로 추상화하는 발상을 하지 못한 경우에는 이를 도출하기 힘들다.

그래서 나는 분리자의 크기를 최소화하는 것을, 일종의 ‘구덩이 메우기’와 같은 느낌으로 해석한 탓에 위와 같은 애드 혹 풀이를 고안하게 되었다. 각종 예외 케이스를 포함하여 글로 풀어내려다보니 장황한 것이지, 실제로는 격자에 그림 몇 번 그려보고 이정도면 되겠거니 싶어 코드를 짜기 시작했다.

문제도 해법도 글로 표현하는 것은 정말 까다로운 일이라는 사실을 느낄 수 있었다. 블로그 포스트는 알고리즘 대회 본문처럼 엄밀할 필요가 있는 것은 아니니 어느 정도의 깊이로 글을 전개할 지 계속 고민해봐야겠다.