[Algorithm🧬] 백준 5846 : Tractor

문제

처음에 생각한 것.

처음에는 올라가는 것만 성능이 필요하다고 생각해서,
일단 제일 작은 지점에서 시작해서 주변 지점에서 가장 작게 오를 수 있는 높이를 배열에 저장하고,
그 작게 오를 수 있는 높이 개수를 작은 것부터 세서 25개 넘어가는 높이를 내보냈는데,

틀린점1. 내려가는 것도 성능이 필요함.
틀린점2. 둘 사이의 높이 차이가 없는게 하나라도 있으면 그 근처 전체 배열이 0 이 되어버림
틀린점3. 가장 작은 지점에서만 시작하는게 아님..

-> 그래서 일단 성능이
0 1000000
0 0

일 때 1000000 까지 가능하니까 성능 기준으로 생각하면 안되겠다 하고 BFS 로 높이차를 저장해서 조질 생각만 했는데,
성능 기준으로 생각하는게 맞는거였음. 이진탐색으로......

import sys
from collections import deque
readl = sys.stdin.readline

def BFS():
    q = deque()

    # 제일 작은 점에서 시작 -> 이 가정이 틀렸음.
    min_str = 1000001
    min_x, min_y = -1, -1
    for i in range(N):
        for j in range(N):
            if min_str > farm[i][j]:
                min_str = farm[i][j]
                min_x, min_y = (i, j)
    
    q.append((min_x, min_y))
    visited[min_x][min_y] = 0

    while q:
        x, y = q.popleft()


        # 제일 작은점 상하좌우로
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy

            if not 0 <= nx < N:
                continue
            if not 0 <= ny < N:
                continue

            # 거기를 올라가려면 힘이 얼마나 필요한지 적음.
            if farm[nx][ny] - farm[x][y] > 0:
                strength = (farm[nx][ny] - farm[x][y])
            # 내려갈때는 지금 힘이면 필요 없다고 생각했는데,
            # 이것도 문제 조건이랑 안맞음.... 잘못 읽음.
            else:
                strength = visited[x][y]

            if visited[nx][ny] <= strength:
                continue

            visited[nx][ny] = strength
            q.append((nx, ny))




N = int(readl())
farm = [list(map(int, readl().split())) for _ in range(N)]

# 해당 칸에 방문하려면 얼마의 성능이 필요한지 갱신.
visited = [[1000001] * N for _ in range(N)]

최소방문칸수 = ((N * N) + 1) // 2

# for i in range(N):
#     print(visited[i])

# print()

BFS()


# for i in range(N):
#     print(visited[i])

# 제일 작은 점에서 힘을 얼마나 써서 갈 수 있는지를 저장한 배열 visited 에 저장된
# 농장의 반을 방문하려면 얼마만큼의 힘이 필요한지를
# 힘 -> 카운트 로 샜음.
visited_cnt = [0] * 1000000
for i in range(N):
    for j in range(N):
        visited_cnt[visited[i][j]] += 1

sum = 0
for i in range(len(visited_cnt)):
    sum += visited_cnt[i]
    if sum >= 최소방문칸수:
        print(i)
        break

진짜 답 : 이진탐색 + BFS

미친 문제인듯...

import sys
from collections import deque
readl = sys.stdin.readline

def BFS(i, j, mid):
    q = deque([(i, j)])
    ch[i][j] = 1
    cnt = 1

    while q:
        x, y = q.popleft()

        if cnt >= 최소방문개수:
            return cnt
        
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy

            if not 0 <= nx < N or not 0 <= ny < N or ch[nx][ny] == 1:
                continue

            strength = abs(farm[nx][ny] - farm[x][y])

            if strength > mid:
                continue

            q.append((nx, ny))
            ch[nx][ny] = 1
            cnt += 1

    return cnt



N = int(readl())
farm = [list(map(int, readl().split())) for _ in range(N)]

최소방문개수 = (N * N + 1) // 2

# print(BFS(0, 0, 1))

# 트랙터의 힘이 mid 일 때,
# 농장의 모든 곳에서 시작해서 몇 개까지 갈 수 있는지 알아본다.
# 그게 반보다 더 많으면 d 를 크게 만들어야하고
# 반보다 더 작으면 d 를 작게 만들어야 함.
max_farm = 0
min_farm = 1000001
for i in range(N):
    for j in range(N):
        if farm[i][j] > max_farm:
            max_farm = farm[i][j]
        if farm[i][j] < min_farm:
            min_farm = farm[i][j]


sol = -1
left = 0
right = max_farm - min_farm

while left <= right:
    mid = (left + right) // 2

    check = 0
    # 이걸 왜 안에 넣어야할까?
    # BFS 에서 해당 지점에서 전부 가는게 아니라 한번 가본 점은 안보고 넘어감.
    # 한번 가본 점 : 어차피 거기로 가서 다시 퍼져봤자 걔 주변에 거리차가 d 보다 큰게 있어서 cnt 가 작게 나올것임. 우린 max 만 구하면 되는데! -> 그래서 빼도 됨.
    ch = [[0] * N for _ in range(N)]
    breaked = False
    for i in range(N):
        for j in range(N):
            # 이런 미친.. ch 배열 안으로 넣고 위에처럼 이유까지 찾아놓고...
            # 이 줄 안넣어서 계속 시간초과남 ㅡㅡ
            if ch[i][j] == 1: continue
            check = max(check, BFS(i, j, mid))
            if check >= 최소방문개수:
                breaked = True
                break
        if breaked:
            break
    
    if breaked:
        right = mid - 1
        sol = mid
    else:
        left = mid + 1

print(sol)