문제
[문제]
n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다.
이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.
이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다.
이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다.
다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.
[출력]
첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.
아이디어
시간 초과가 나지 않는 풀이 방법을 떠올리기 어려웠던 문제로, 참고 사이트에 기재한 블로그들을 보고 풀이했다.
브루트포스 (시간초과)
브루트포스로 모든 (최대 - 최소) 케이스를 찾는 경우, 시간초과가 발생한다.
-
x = 이동하기 위해 거쳐간 수들 중 (최대 - 최소) 라고 하자.
-
배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이므로
x의 범위는 0 이상 200 이하이다. -
x가 0일 때 배열의 (n, n)위치까지 도달하기 위해 지나는 칸의 최대값과 최소값을 <최대값, 최소값>으로 표시해보면
-
<0, 0>, <1, 1>, ... <200, 200> 으로 201개의 쌍이 있다.
-
x가 1일 때의 <최대값, 최소값>은
- <1, 0>, <2, 1>, ... <200, 199> 로 200개의 쌍이 있다.
-
x가 200일 때의 <최대값, 최소값>은
- <200, 0>으로 1개의 쌍이 있다.
-
-
즉, 최악의 경우 201 + 200 + 199 + ... + 3 + 2 + 1 = 약 20,000개의 케이스를 검사해야하는데 각 케이스에서 배열을 순회하는 데 O(N^2)이 소요된다.
-
따라서 총 시간복잡도는 O(20,000 * N^2)
이분탐색
시간복잡도를 줄이기 위해 이분탐색을 적용한다.
1️⃣ 이분 탐색의 범위는 아래와 같이 설정한다.
-
left = 왼쪽 포인터 = 초기값 0
-
right = 오른쪽 포인터 = 초기값 (배열의 최대값 - 배열의 최소값)
-
mid = (left + right) / 2 = 왼쪽 포인터와 오른쪽 포인터의 중간 값.
2️⃣ 이동하기 위해 거쳐간 수들 중 (최대 - 최소)를 mid로 만들 수 있는지 확인하는 방법은 아래와 같다.
-
차이를 mid로 만들 때, 지날 수 있는 칸의 <최대값, 최소값> 범위를 정한다.
- 최소값이 val일 때, 최대값은 val + mid가 되겠다.
-
bfs를 하며 <최대값, 최소값> 범위 내에 있는 칸만을 지나며 (1, 1) 에서 (n, n)까지 도달할 수 있는지 검사한다.
-
<최대값, 최소값> 쌍 중 하나라도 bfs에 성공한다면 이동하기 위해 거쳐간 수들 중 최대값과 최솟값의 차이를 mid로 만들 수 있다.
3️⃣ 이분탐색을 계속한다.
- 이동하기 위해 거쳐간 수들 중 최대값과 최솟값의 차이를 mid로 만드는 데 성공했다면
- 최대값과 최소값의 차이를 더 줄여볼 수 있다.
right = mid - 1
- 이동하기 위해 거쳐간 수들 중 최대값과 최솟값의 차이를 mid로 만들지 못했다면
- 최대값과 최소값의 차이를 더 크게 해서 검사해본다.
left = mid + 1
제출 코드
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
min_arr = min(map(min, arr))
max_arr = max(map(max, arr))
max_diff = max_arr - min_arr
def bfs(min_val, max_val):
# min_val 이상, max_val 이하의 값을 지나며
# (n-1, n-1)까지 도달할 수 있는가?
if arr[0][0] < min_val or arr[0][0] > max_val:
return False
visited = [[False] * n for _ in range(n)]
visited[0][0] = True
q = deque([(0, 0)])
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
while q:
r, c = q.popleft()
if r == n-1 and c == n-1:
return True
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if not(0 <= nr < n and 0 <= nc < n):
continue
if arr[nr][nc] < min_val or arr[nr][nc] > max_val:
continue
if visited[nr][nc]:
continue
visited[nr][nc] = True
q.append((nr, nc))
return False
def solve(goal):
# 차이를 goal로 만들면서 (0, 0)에서 (n-1, n-1)까지 도달할 수 있는가?
# 차이를 goal로 만들 때, 지날 수 있는 최소값은 min_val이고 최대값은 min_val + goal이다.
for min_val in range(min_arr, max_arr + 1):
max_val = min_val + goal
if max_val > max_arr:
break
if bfs(min_val, max_val):
return True
return False
left = 0
right = max_diff
answer = max_diff
# 이분탐색
while left <= right:
mid = (left + right) // 2
success = solve(mid)
if success:
answer = min(answer, mid)
# 차이를 mid로 만드는 데 성공했다면, 차이를 더 줄여볼 수 있다.
right = mid - 1
else:
left = mid + 1
print(answer)- 메인 이분탐색 부분의 시간복잡도가 O(log200)정도
- solve 함수에서 지날 수 있는 최소값과 최대값의 범위를 구하는 부분의 시간복잡도가 O(200)정도
- bfs를 하는 부분의 시간복잡도가 O(N^2)정도로
- O(log200 * 200 * N^2) = 7 * 200 * 100 * 100 = 14,000,000 번의 연산을 수행할 것으로 예상된다.
참고 사이트
