백준 3108번: 로고 (Kotlin)

https://www.acmicpc.net/problem/3108

3108번: 로고

안녕하세요, 이륙사입니다.

 

풀이

이번 문제는 Union-Find 혹은 BFS, DFS를 사용해서 해결할 수 있는 문제였습니다. 그중에서 이번엔 BFS를 사용해서 포스팅해보려고 합니다.

 

먼저, 예시들을 통해 PU의 개수는 직사각형의 수와 관련이 있다는 걸 알 수 있습니다. 그리고 만약 한점 이상에서 만나는 직사각형들이 있다면 그 직사각형들은 연필을 떼지 않고 한번에 그릴 수 있습니다. 즉, 몇 번의 한붓 그리기로 모든 직사각형들을 그릴 수 있는지 묻고 있으며, 직사각형 집합의 개수를 구하는 문제로도 생각할 수 있습니다. (참고로 직사각형만 그릴 수 있기 때문에, 2, 3번 명령어는 고려하지 않아도 됩니다.)

 

따라서 집합의 수를 구하기 위해 Union-Find를 떠올릴 수 있으며, 겹치는 직사각형의 점들은 모두 연결되어 있기 때문에 인접한 곳을 모두 탐색하는 BFS, DFS로도 해결할 수 있게 되는 겁니다! 탐색 함수를 호출한 횟수가 집합의 개수가 됩니다. 

for (y in 0 until MAX_PLUS_ONE) {
        for (x in 0 until MAX_PLUS_ONE) {
            if (graph[y][x] == 1 && visited[y][x].not()) { // 직사각형이 있고, 아직 그룹지어지지 않았다면
                answer += 1
                bfs(x, y)
            }
        }
    }

 

 

좌표 변환

단순 그래프 탐색 문제가 되었으므로, 열심히 구현해서 정답을 제출합니다. 그리고 틀립니다. 왜냐면 아래와 같이 겹치지 않는데도 인접하는 상황이 발생하기 때문입니다.

 

이럴 때 좌표 값을 2배 늘려주면, 거리가 1이던 점들의 거리도 2가 돼서 문제를 해결할 수 있습니다! 또한, 좌표값은 양수이어야 하므로 먼저 +500 증가시킨 후에 좌표 값을 2배 늘려줍니다.

repeat(n) {
        val st = StringTokenizer(readLine())
        drawRect(2 * (st.nextToken().toInt() + 500), // 좌표를 오른쪽으로 이동 후 2배 증가
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500)
        )
    }

 

디버깅을 통해서나 아니면 처음부터 이런 상황을 떠올릴 수 있으면 정말 좋겠지만, 문제 경험이 풍부하지 않고선 쉽지 않을 것 같습니다ㅋㅋ

 

 

예외 처리

정말 마지막으로, 처음에 (0, 0)에서 연필을 내린 상태로 시작한다는 점도 주의해주셔야 합니다. (0, 0)과 이어진 사각형들은 처음에 연필을 올리지 않고 그릴 수 있기 때문입니다. 

// 처음에 (1000,1000)에 연필을 내린 상태에서 시작
if (graph[1000][1000] == 1) print(answer - 1)
else print(answer)

 

생각 과정

1. 예시를 통해 사각형 집합의 개수를 구하는 문제라는 것을 확인한다.
2. 그래프 안에서 집합의 개수를 구하는 방법을 떠올린다 -> Union-Find, DFS, BFS

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

const val MAX_PLUS_ONE = 2001

val graph = Array(MAX_PLUS_ONE){
    IntArray(MAX_PLUS_ONE)
}
val visited = Array(MAX_PLUS_ONE) {
    BooleanArray(MAX_PLUS_ONE)
}
val dX = arrayOf(-1, 1, 0, 0)
val dY = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var puCount = 0

    repeat(n) {
        val st = StringTokenizer(readLine())
        // 좌표를 오른쪽으로 이동 후 2배 증가
        val x1 = 2 * (st.nextToken().toInt() + 500); val y1 = 2  * (st.nextToken().toInt() + 500)
        val x2 = 2 * (st.nextToken().toInt() + 500); val y2 = 2 * (st.nextToken().toInt() + 500)

        drawRectangle(x1, y1, x2, y2)
    }

    for (y in 0 until MAX_PLUS_ONE){
        for (x in 0 until MAX_PLUS_ONE) {
            // 직사각형이 있고, 아직 그룹지어지지 않았다면
            if (graph[y][x] == 1 && visited[y][x].not()) {
                bfs(x, y)
                puCount++
            }
        }
    }

    // 연필은 (1000,1000)에 내린 상태에서 시작한다
    if (graph[1000][1000] == 1) print(puCount - 1)
    else print(puCount)
}

// 직사각형 그리기
fun drawRectangle(x1: Int, y1: Int, x2: Int, y2: Int) {
    for (i in y1..y2) {
        graph[i][x1] = 1
        graph[i][x2] = 1
    }

    for (i in x1 + 1 until x2) { // 변끼리 겹치는 점 제외
        graph[y1][i] = 1
        graph[y2][i] = 1
    }
}

fun bfs(startX: Int, startY: Int) {
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(startX, startY))
    visited[startY][startX] = true

    while (q.isNotEmpty()) {
        val (x, y) = q.poll()

        for (i in 0 until 4) {
            val nextX = x + dX[i]
            val nextY = y + dY[i]

            if (nextX !in 0 until MAX_SIZE || nextY !in 0 until MAX_SIZE) continue

            if (graph[nextY][nextX] == 1 && visited[nextY][nextX].not()) {
                visited[nextY][nextX] = true
                q.add(Pair(nextX, nextY))
            }
        }
    }
}