[BOJ] Q2842 집배원 한상덕

[BOJ] Q2842 집배원 한상덕

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 bfs와 two-pointer을 결합한 유형의 문제이다. 이번 문제의 핵심은 고도를 활용하여 bfs 탐색 처리를 진행해야한다는 점이다. 최소 피로도(높이차)를 유지하면서 모든 집을 방문하기 위해서는 방문하는 노드의 높이의 범위를 최소화하는 것이 목표이다. 따라서, 해당 지도에서 가질 수 있는 모든 높이를 구해서 이를 정렬한다음, two-pointer을 활용하여 범위를 구한다.

제한을 둔 bfs을 생각해내는 것이 문제의 핵심이다.

높이 배열

height_list=set()
for row in range(n):
    for col in range(n):
        height_list.add(heights[row][col])
        if board[row][col]=="P":
            start_row,start_col=row,col
        if board[row][col]=="K":
            houses+=1

height_list=sorted(list(height_list))

Two pointer + BFS

최소 높이와 최대 높이를 고정한 상태로 bfs을 수행하여 도달가능한 집의 총 갯수를 구한다. 이때 만약 모든 집을 도달할 수 있는 경우에는 left 값을 올려서 범위를 축소시킨다. 만약, 모든 집을 방문하지 못한 경우에는 right 값을 키워서 탐색 범위를 넓히도록 한다.

length_of_height_list=len(height_list)
left,right=0,0
while left < length_of_height_list:
    result=bfs(start_row,start_col,height_list[left],height_list[right])
    #모든 집을 다 방문한 경우, left값을 올려서 범위를 축소한다.
    if result == houses:
        answer=min(answer,height_list[right]-height_list[left])
        left+=1
    #모든 집을 방문하지 못했고, 탐색 가능한 right 범위가 있는 경우 right 값을 올린다.
    elif right + 1 < length_of_height_list:
        right+=1
    #더 이상 탐색 가능한 left,right 범위가 없는 경우 탈출한다.
    else:
        break

Solution

from math import inf
from collections import deque

def bfs(start_row,start_col,min_height,max_height):

    dy=[-1,-1,-1,0,1,1,1,0]
    dx=[-1,0,1,1,1,0,-1,-1]

    queue=deque([(start_row,start_col)])
    house_count=0
    visited=[[False] * n for _ in range(n)]

    #시작점이 최소,최대 높이 범위에 해당되지 않은 경우 바로 반환
    if heights[start_row][start_col] < min_height or heights[start_row][start_col] > max_height:
        return 0
    
    while queue:
        row,col=queue.popleft()

        #이전에 방문한 경우
        if visited[row][col]:
            continue
        visited[row][col]=True
        
        #집인 경우
        if board[row][col]=="K":
            house_count+=1

        for dir in range(8):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            #격자를 넘어서는 경우
            if next_row < 0 or next_row>=n or next_col < 0 or next_col>=n:
                continue
            #탐색하고자 하는 집의 높이가 최소, 최대 범위에 해당하지 않는 경우
            if heights[next_row][next_col] < min_height or heights[next_row][next_col] > max_height:
                continue

            queue.append((next_row,next_col))

    return house_count

def solution():
    houses=0
    answer=inf
    start_row,start_col=0,0
    height_list=set()
    for row in range(n):
        for col in range(n):
            height_list.add(heights[row][col])
            if board[row][col]=="P":
                start_row,start_col=row,col
            if board[row][col]=="K":
                houses+=1

    height_list=sorted(list(height_list))
    length_of_height_list=len(height_list)
    left,right=0,0
    while left < length_of_height_list:
        result=bfs(start_row,start_col,height_list[left],height_list[right])
        if result == houses:
            answer=min(answer,height_list[right]-height_list[left])
            left+=1
        elif right + 1 < length_of_height_list:
            right+=1
        else:
            break

    print(answer)

if __name__ == "__main__":
    n=int(input())
    board=[list(input().strip()) for _ in range(n)]
    heights=[list(map(int,input().split())) for _ in range(n)]

    solution()