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)
마무리
시간 복잡도 계산이 조금 복잡했던 문제였다.
시간 복잡도 계산만 잘 했다면 굉장히 쉽게 풀 수 있던 문제였는데 잘못 계산하여 삽질을 너무 많이 했다.
'백준 알고리즘' 카테고리의 다른 글
[CodeTree] 십자 모양 폭발 (중력) (0) | 2024.08.24 |
---|---|
[CodeTree] 삼각형 컨베이어 벨트 (0) | 2024.08.23 |
[CodeTree] 우리는 하나 (0) | 2024.08.17 |
[백준 16500][파이썬] 문자열 판별 (dfs) (0) | 2023.07.06 |
[백준 1080, 2138][파이썬] 행렬, 전구와 스위치 (그리디 알고리즘) (0) | 2023.06.30 |
댓글