[백준] 2842번 집배원 한상덕

🔔 문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다..

출력
첫째 줄에 가장 작은 피로도를 출력한다.

🎯 풀이방법

BFS + 투 포인터 문제이다.

board : 마을
altitude : 지역의 고도
houses : 전체 K의 갯수
fatigue : 모든 고도의 종류
left, right : 투 포인터
px, py : 시작점
answer : 가장 작은 피로도

1. 시작점, 총 집의 갯수, 고도 종류 설정하기
   1-1. 시작점 : 우체국의 위치
   1-2. 총 집의 갯수 : K 갯수
   1-3. 고도 종류 : 모든 고도의 종류

2. 모든 고도의 종류(fatigue)를 생성

   • 지역의 고도(altitude)를 set과 정렬을 통해 중복을 제거

3. 시작점의 고도가 최소(left) ~ 최대(right) 고도 사이일 경우에만 BFS를 시작한다. BFS 탐색 시에 집을 방문할 때마다 K를 1씩 증가한다.

4. 모든 집(houses)을 방문했을 때 최소 피로도를 구한다.

5. 4가 아닐 경우에, 최대(right)가 남아있을 경우 right을 1 증가한다.

6. 4,5 모두 아닐 경우 종료한다.

7. 최소 피로도를 출력한다.
   
   

위의 예제를 1~7번 알고리즘 대로 수행한다면 아래 그림과 같이 7번의 while문을 돌게 된다. 배열은 고도를 오름차순으로 정렬한 배열이며, left와 right은 각각 이 배열의 원소를 가리킨다.

시작점이 최소 ~ 최대 범위에 속할 때만 BFS 탐색을 수행한다. BFS 탐색은 총 5번 수행되며 아래의 그림은 BFS를 수행할 때 탐색한 경로를 표시한 것이다. (3,4,5,6번 알고리즘)

🙄 놓쳤던 점

최소(left) ~ 최대(right) 고도 범위에 따라 BFS를 탐색한다는 점을 생각 못했다. 범위에 해당되는 모든 값들을 탐색하고 그 값들 중에서 집의 갯수를 센다.

💡 이 문제를 통해 얻어갈 것

BFS와 투 포인터 개념을 결합한 문제

💻 Python 코드

import sys
from collections import deque

# 위, 아래, 좌, 우, 대각선
dr = [-1,1,0,0,-1,1,1,-1]
dc = [0,0,-1,1,-1,-1,1,1]

# BFS + 투 포인터
N = int(input())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]
altitude = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

houses = 0
fatigue = []

for i in range(N):
    for j in range(N):
        if board[i][j] == 'P':
            px, py = i, j
        elif board[i][j] == 'K':
            houses += 1
        fatigue.append(altitude[i][j])

# 1. 입력받은 pirodo에 대해서 정렬 and set을 통한 중복 제거
fatigue = sorted(set(fatigue))
#print("fatigue : ", fatigue)

left, right = 0,0
answer = sys.maxsize


def bfs(start_x,start_y):
    visit = [[False]*N for _ in range(N)]
    queue = deque([(start_x,start_y)])
    visit[start_x][start_y] = True
    K = 0   # 방문한 집의 갯수

    while queue:
        # print("queue : ", queue)
        x,y = queue.popleft()
        #print("{}, {} pop".format(x,y))

        # 수직, 수평, 대각선 탐색
        for i in range(8):
            nx,ny = x+dr[i], y+dc[i]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if visit[nx][ny]:
                continue

            tired = altitude[nx][ny]

            # 현재 피로도가 left, right 사이일 경우에만 추가로 탐색
            if fatigue[left] <= tired <= fatigue[right]:
                #print("좌표={},{} , 피로도={} ({}~{})".format(nx,ny,tired,fatigue[left],fatigue[right]))

                visit[nx][ny] = True
                queue.append((nx,ny))

                # 집이면 K 증가
                if board[nx][ny] == 'K':
                    K += 1
    return K


while left<len(fatigue):
    #print("left : ", left,", right : ",right, end='  - ')
    #print("{} ~ {}".format(fatigue[left], fatigue[right]))
    K=0

    # 3. 시작점의 고도가 최대 고도와 최소 고도 사이일 경우에만 BFS를 시작
    if fatigue[left] <= altitude[px][py] <= fatigue[right]:
        #print("BFS start!")
        K = bfs(px, py)

    # 집을 모두 방문함
    if K == houses:
        # 최소 피로도 구하기
        answer = min(answer, fatigue[right]-fatigue[left])
        #print("집을 모두 방문! answer : ", answer)

        left += 1  # 최소 높이 증가
    elif (right+1) < len(fatigue):
        # 아직 최대고도가 남아있을 때 최대 고도 증가
        #print("아직 최대 고도가 남음.. ")
        right += 1
    else:
        #print("모두 아닐 때,, ")
        break
    #print()

print(answer)