[CodeTree] 격자 칠하기 2

https://www.codetree.ai/missions/8/problems/painting-the-grid-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

알고리즘

• bfs
• parametric search

 

이 문제는 결정 문제로 변환한 뒤 이진 탐색을 진행하는 평범한 parametric search 문제이다.

 

bfs와 parametric search 기본 지식이 있으면 풀 수 있는 문제지만 초반에 시간 복잡도 계산을 잘못해서 한참 삽질을 해서 가져와 보았다.

 

이진 탐색으로 d의 범위를 좁히면서 조건을 만족하는 가장 작은 d를 찾으면 된다.

 

d의 값이 n일 때 문제의 조건을 만족한다고 했을 때 d의 값이 n보다 크다면 무조건 조건을 만족하게 되고 이는 parametric search를 적용할 수 있다는 말이 된다.

 

d의 값이 주어졌을 때 bfs를 통해 격자를 모두 탐색하여 격자 개수의 절반 이상을 방문할 수 있는지 확인한다.

 

d의 값은 이진 탐색을 통해 계속 범위를 줄이면서 위 과정을 반복하면 된다.

 

잘못 생각한 알고리즘

내가 가장 많이 고민했던 부분은 "임의로 시작칸을 잘 정한 후"라는 문장이었다.

 

시작칸이 고정되어 있지 않아서 2차원 배열을 모두 순회하면서 모든 좌표에서 bfs를 진행해야 한다고 판단했다.

 

우선 하나의 시작칸을 정해서 bfs를 진행했을 때 시간 복잡도는 O(n^2)이 된다.

 

그리고 모든 칸에 대해서 bfs를 진행해야하기 때문에 d 값에 대해 문제의 조건을 만족시키는지 확인하기 위한 시간 복잡도는 O(n^4)가 된다.

 

여기에 d 값에 대해서 이진 탐색을 하기 때문에 log(d)를 추가하면 총 알고리즘은 (O(N^4log d)) 이 된다.

 

n의 최대 값은 100이고 100의 4제곱은 1억에 가깝다.

 

여기에 d의 최대값은 1,000,000이고 여기에 로그를 씌우면 약 20이다.

 

최악의 경우 20억 번 반복을 진행하게 되는데 1억 번 반복이 1초 정도 걸리기 때문에 시간 초과가 날 수밖에 없다.

 

알고리즘 개선

 

하지만 모든 시작 점에 대해서 bfs를 진행할 필요가 없다.

 

아래와 같은 격자에서 이 문제를 해결한다고 하자.

 

 

d가 0이고 (0, 0) 좌표를 방문했다고 해보자.

 

결과는 총 4개가 나왔고 조건을 만족시키지 못했다,

 

이제 다른 좌표를 시작점으로 잡아서 확인을 해야 한다.

 

그런데 여기서 이미 방문한 좌표는 방문할 필요가 없다.

 

어차피 결과는 똑같기 때문이다.

 

즉 특정 d에 대해서 조건을 만족하는지 확인할 때 방문 배열을 하나로 두고 이미 방문한 곳은 방문할 필요가 없다.

 

시작 점을 고를 때도 마찬가지이고 bfs를 진행할 때도 마찬가지이다.

 

이렇게 하면 d에 대해서 조건을 만족하는지 판단하는 알고리즘의 시간 복잡도가 O(n^2)이 된다.

 

즉 총 시간복잡도는 (O(N^2log d)) 이 되고 최악의 경우에 200,000 번 반복을 진행한다.

 

시간 복잡도가 많이 줄어들었고 시간 초과가 발생하지 않는다.

 

import sys
input = sys.stdin.readline

# 동서남북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

# (x, y)에서 시작했을 때 색칠 가능한 칸의 개수
def bfs(x, y, visited, d):
    visited_cnt = 1
    queue = [(x, y)]
    visited[x][y] = True
    while queue:
        x, y = queue.pop()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and abs(arr[x][y] - arr[nx][ny]) <= d:
                visited_cnt += 1
                queue.append((nx, ny))
                visited[nx][ny] = True
    return visited_cnt
# 임의로 시작칸을 잘 정한 후, 
# 칸에 쓰인 숫자가 현재 칸의 숫자와 D 이하로 차이나는 상, 하, 좌, 우로 인접한 칸으로 이동했을 때
# 색칠된 칸이 전체 칸의 반 이상이 될 수 있는지
def is_possible(d):
    visited = [[False]*n for _ in range(n)]
    # 모든 시작 점
    for i in range(n):
        for j in range(n):
            visited_cnt = bfs(i, j, visited, d)
            if visited_cnt >= round((n**2)//2):
                return True
    return False

def parametric_search():
    res = 1000000
    left, right = 0, 1000000
    while left <= right:
        mid = (left + right)//2
        # 가능하다면 더 작은 범위 체크
        if is_possible(mid):
            right = mid - 1
            res = min(res, mid)
        else:
            left = mid + 1
    return res

res = parametric_search()
print(res)

 

 

마무리

시간 복잡도 계산이 조금 복잡했던 문제였다.

 

시간 복잡도 계산만 잘 했다면 굉장히 쉽게 풀 수 있던 문제였는데 잘못 계산하여 삽질을 너무 많이 했다.