(BOJ) 2288 격자의 분리자

2288 격자의 분리자

문제

연결된, 무향 그래프 G=(V, E)가 주어졌을 때, V가 정점의 집합을 나타내고, E가 간선의 집합을 나타낸다고 하자.

V의 부분집합 S를 G에서 제거했을 때, 그래프가 두 개의 연결 요소로 나눠지면 S를 분리자라고 한다.

그래프에서 정점을 제거하면 제거한 정점에 연결된 간선도 함께 제거된다.

이와 같은 상황을 [S, W, B] 라는 기호로 나타내기로 하자.

이는 그래프가 분리자 S에 의해서 W와 B라는 두 개의 연결 요소로 나뉘어 진다는 의미이다.

우리는 격자 모양의 그래프에서의 분리자를 살펴보려 한다.

이 그래프에서 각각의 격자점이 정점을 이루며, 각각의 정점은 이웃한 8개의 정점들과 연결되어 있다.

아래에 6×6 격자 에 대한 예제 그림이 있다. 흰색은 W, 회색은 S, 검은색은 B를 나타낸다.

문제를 단순화하기 위해, 다음의 조건을 만족하는 분리자만 다루기로 하자.

1. 분리자의 부분집합은 분리자를 이루지 않는다.
2. 분리자는 그래프에서 맨 윗줄의 한 점과 맨 아랫줄의 한 점을 포함한다. 단, 0, 5, 30, 35는 제외한다.
3. 분리자를 따라서 그래프를 위에서 아래로 이동할 때, 내려오다가 다시 올라가는 경우는 없다.

이제 다음의 두 단계를 수행하여 분리자의 크기를 줄이려고 한다.

1. B에서 몇 개의 정점을 택해서 S에 포함시킨다. 이때 택한 정점들은 반드시 왼쪽 정점으로 S에 포함된 정점을 가지고 있어야 한다.
2. S에서 몇 개의 정점을 제거하여 W에 포함시킨다. 단, 이전 단계에서 포함시킨 정점들은 제거할 수 없다.

이와 같은 개선 방법을 이용하여 S가 여전히 분리자이도록 하고, 이때 S의 크기를 최소로 하라. 위의 예제는 다음과 같이 하면 S의 크기가 7로 최소가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

첫째 줄에 격자의 크기를 나타내는 두 정수 N, M(3 ≤ N, M ≤ 200)이 주어진다.

이는 격자의 크기가 N×M이라는 의미이다.

다음 N개의 줄에는 M개의 문자가 주어지는데, 각각은 S, W, B 중의 하나이다.

이는 해당 정점이 S, W, B 중 어느 집합에 속해있는지를 나타낸다.

W는 반드시 S의 왼쪽에 존재한다.

잘못된 입력이 주어지지는 않는다고 가정해도 좋다.

모든 문자는 붙어서 입력된다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

첫째 줄에 S의 최소 크기를 출력한다.

예제 입력 1

6 6
WWSBBB
WSSBBB
WSBBBB
WSBBBB
WSSSBB
WWWSBB
0 0

예제 출력 1

7

Solution

Expander

import java.util.*


private const val WHITE = 'W'
private const val SEPARATION = 'S'
private const val BLACK = 'B'

private const val INIT = -1
private const val LEFT = 0
private const val RIGHT = 1


private var N: Int = 0
private var M: Int = 0

private var map: Array<String> = arrayOf()

fun main() {
    input()
}

private fun input() = with(Scanner(System.`in`)) {
    while (true) {
        N = nextInt()
        M = nextInt()
        if (N + M == 0) {
            return
        }
        map = Array(N) { "" }
        for (i in 0 until N) {
            map[i] = next()
        }
        solve()
    }
}

private fun solve() {
    var direction = INIT
    var result = 1
    var y = map[0].indexOf(SEPARATION)

    for (x in 0 until N) {
        if (y != 0 && map[x][y - 1] == SEPARATION) {
            direction = LEFT
            while (y > 0 && map[x][y - 1] == SEPARATION) {
                y--
                result++
            }
            result++
            continue
        }

        if (y + 1 < M && map[x][y + 1] == SEPARATION) {
            if (direction == INIT) {
                result--
            }
            if (direction == LEFT) {
                result -= 2
            }
            direction = RIGHT
            while(y + 1 < M && map[x][y + 1] == SEPARATION) {
                y++
                result++
            }
            result++
            continue
        }
        result++
    }

    if (direction == LEFT) {
        println(result - 2)
    } else {
        println(result - 1)
    }
}

Point of Thinking

• 단순 구현 문제이다.
• 분리자는 절대 양끝에 닿지않는다.
• 좌우로 펼쳐진 분리자는 B 혹은 W로 변경하여 최소화한 것처럼 처리해도 정답이 나온다.
• 문제의 조건과 테스트 케이스만 대응하여도 Accepted