백준 1074번: Z (Kotlin)

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

1074번: Z

 

풀이

같은 유형의 작은 문제들로 계속 쪼개어지는 것으로 보아, 분할 정복 문제라는 것을 알 수 있었다. 그치만 시간 제한이 0.5초라서 주의해야 할 부분이 있었다.

 

행렬 표현

먼저 탐색에 앞서 행렬은 시작점과 각 변의 길이를 통해 나타낼 수 있다.

행렬 표현

 

1. 시간 제한을 고려하지 않는 방법

1. (0, 0)과 전체 크기의 행렬을 대상으로 탐색을 시작한다.
2. 지금 탐색중인 행렬의 길이를 확인한다.
   1. 2보다 길거나 같으면, 길이를 2로 나눠서 Z모양에 따라 다시 재귀적으로 탐색한다.
   2. 길이가 1이고,
      1. 목표 지점이라면, 몇 번째로 방문했는지 저장하고 탐색을 종료한다.
      2. 목표 지점이 아니라면,해당 점의 위치를 확인하고 방문 순서(count)를 +1 증가시키고 재귀 탐색을 종료한다.
3. 목표점의 방문 순서를 출력한다.

이렇게 하면 항상 정답을 찾을 수 있다. 하지만 코드를 제출해보면 시간 초과가 발생한다.

 

📌시간 복잡도)

- (2^n * 2^n) 행렬의 길이가 1(한 점)이 될 때까지 2로 나누는 횟수 = log(2^n) = n

- 모든 점의 개수 = 2^n * 2^n

연산 횟수: (2^n * 2^n) * n = 2^15 * 2^ 15 * 15 = 약 160억

시간 복잡도: O(n*4^n)

 

따라서, 연산 횟수를 줄여야 한다. 그리고 아래의 그림과 같이 찾는 점이 존재하는 구간만 재귀적으로 탐색하면 시간 복잡도를 확 줄일 수 있다. 나머지 부분은 방문 순서만 업데이트 해준다.

 

2. 시간 복잡도를 개선한 방법

필요한 곳만 탐색

 

1. (2^n * 2^n) 행렬을 Z모양의 순서대로 탐색한다.
2. 지금 탐색중인 범위가 내가 찾으려고 하는 최종 범위(점)인지 확인한다.
   1. 찾던 점이라면, 몇 번째로 방문했는지 저장한다.
   2. 아니라면, Z방향 순서대로
      1. 목표지점을 포함하지 않는 곳은 방문 순서(visitCount)만 길이 * 길이만큼 증가시키고 탐색을 종료한다
      2. 목표지점을 포함하는 곳은 길이를 절반으로 나눠서 탐색을 계속한다.
3. 목표점의 방문 순서를 출력한다.

📌줄어든 시간 복잡도)

- 필요한 점을 찾기 위해 구간을 나누는 횟수 = log(2^n) = n,

- 나눌 때마다 방문 순서 업데이트 하는 연산 횟수 3번

연산 횟수: 3 * n = 3 * 15 = 45

시간 복잡도: O(n)

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader

var answer = 0
var numbering = 0

// dudwls901님 풀이 참고 버전

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ").map{ it.toInt() }
    val (n, r, c) = input

    visitGraph(1 shl(n), 0, 0, r, c)
    print(answer)
}

fun visitGraph(size: Int, row: Int, col: Int, targetRow: Int, targetCol: Int) {

    // 탐색중인 Z구간에 목표지점이 없으면
    // 탐색하지 않고 방문 순서만 update하고 탐색을 종료한다
    if (targetRow !in row until row + size || targetCol !in col until col + size) {
        numbering += size * size
        return
    }

    // 목표지점을 찾았으면 방문 순서를 저장하고 리턴한다
    if (row == targetRow && col == targetCol) {
        answer = numbering
        return
    }

    val halfSize = size / 2

    visitGraph(halfSize, row, col, targetRow, targetCol) // 왼쪽 위
    visitGraph(halfSize, row, col + halfSize, targetRow, targetCol) // 오른쪽 위
    visitGraph(halfSize, row + halfSize, col, targetRow, targetCol) // 왼쪽 아래
    visitGraph(halfSize, row + halfSize, col + halfSize, targetRow, targetCol) // 오른쪽 아래
}