문제 : https://www.acmicpc.net/problem/2842

문제

P에서 모든 K를 방문할 수 있는 고도들을 구하면 된다.
필자는 단순히 binary search를 이용해서 문제를 풀고자 했으나 key값을 뭐로 두어야 될지 몰라 결국 구글링을 해보니 기가 막힌 전략이 있었다...

풀이

reference : https://comyoung.tistory.com/279

binary search가 아닌 투포인터를 이용하여 지나갈 수 있는 고도들을 정해주는 것이다. 즉, 0~max(board) 의 arr를 선언해주고 정렬을 한 후 투포인터를 이용하여 지나갈 수 있는 고도의 범위를 정해서 bfs를 탐방해주면 끝!!
(효율성을 위하여 set을 해주고 sorted를 해주면 중복없이 정렬할 수 있다)

code

from collections import deque

n = int(input())
board = []
board_height = []
n_house = 0
for i in range(n):
    temp = list(input())
    for j in range(n):
        if temp[j]=='P':
            start = (i,j)
        if temp[j]=='K':
            n_house+=1
    board.append(temp)
for _ in range(n):
    board_height.append(list(map(int,input().split())))

def bfs(start, left, right):
    dy = [0,0,-1,1,-1,-1,1,1]
    dx = [-1,1,0,0,-1,1,-1,1]
    q = deque()
    visit = [[False]*n for _ in range(n)]
    y,x = start
    visit[y][x] = True
    q.append(start)
    cnt = 0
    while q:
        y,x = q.popleft()
        if board[y][x]=='K':
            cnt+=1
        if cnt==n_house:
            break
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if not (0<=ny<n and 0<=nx<n):
                continue
            if visit[ny][nx]:
                continue
            if left<=board_height[ny][nx]<=right:
                visit[ny][nx]=True
                #print(y,x, ny,nx,board_height[y][x],board_height[ny][nx],k)
                q.append((ny,nx))
    if cnt==n_house:
        return True
    else:
        return False

def search(start):
    arr = set()
    for height in board_height:
        for h in height:
            arr.add(h)
    arr = sorted(arr)
    
    _min = 0
    _max = 0
    answer = 1000000
    
    while _max<len(arr):
        
        while _min<=_max:
            left = arr[_min]
            right = arr[_max]
            if not (left<=board_height[start[0]][start[1]]<=right):
                break
            check = bfs(start, left, right)
            if check:
                _min+=1
                answer = min(answer, right-left)
            else:
                break
        _max += 1
    return answer
print(search(start))

result

주의할 점으로 P의 위치가 투포인터로 정한 범위 내에 있는지도 탐색해야된다. 이 점을 고려하지 않으니 계속해서 55퍼에서 틀렸습니다가 떴다...