[백준/2842] 집배원 한상덕 (Python)

Problem : https://www.acmicpc.net/problem/2842

2842번: 집배원 한상덕

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:58:05

 

---

 

문제 설명

 

 

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

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

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

 

 

입력 및 출력

 

입력

 

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)
다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.
다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.

 

출력

 

2
P.
.K
2 1
3 2

 

입력 예시

 

0

 

출력 예시

 

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

 

 

---

 

풀이

 

피로도가 "방문한 지점의 최대 고도 - 방문한 지점의 최소 고도" 로 정의된다면, 반대로 "방문한 지점의 최소 및 최대 고도를 제한해보는 게 어떨까?" 라는 생각을 해볼 수 있다.

 

또한, 우리는 무조건 우체국과 집들을 방문해야 한다. 즉 제한되는 최소 및 최대 고도는 이 우체국들과 집들의 고도 범위를 포함해야 한다.

 

이러한 생각을 바탕으로, 우리는 투 포인터를 사용해 볼 수 있겠다. 가능한 최소 고도와 최대 고도 리스트를 만들고, 이들 고도 범위 내를 탐색하는 경로 탐색 알고리즘을 사용한다. 만약 모든 우체국 지점을 방문할 수 있다면 가능한 경우이므로 정답을 (최대 고도 - 최소 고도)로 업데이트한다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [1, 0, -1, -1, -1, 0, 1, 1]
MAX = 1000000

N = int(input())
houses = []
maps = []
for i in range(N) :
  _maps = input().strip()
  for j in range(N) :
    if _maps[j] == 'P' :
      houses.append((j, i))
      sx, sy = j, i
    if _maps[j] == 'K' :
      houses.append((j, i))
  maps.append(_maps)
height = [list(map(int, input().split())) for _ in range(N)]
min_range, max_range = set(), set()
rank = [height[y][x] for x, y in houses]
min_rank, max_rank = min(rank), max(rank)
for i in range(N) :
  for j in range(N) :
    if height[i][j] <= min_rank :
      min_range.add(height[i][j])
    if height[i][j] >= max_rank :
      max_range.add(height[i][j])

min_range = sorted(min_range)
max_range = sorted(max_range)
H = len(houses)

def bfs(minval, maxval) :
  q = deque([(sx, sy)])
  visited = [[False]*N for _ in range(N)]
  visited[sy][sx] = True
  cnt = 1
  while q :
    x, y = q.pop()
    for i in range(8) :
      ax, ay = x + dx[i], y + dy[i]
      if -1 < ax < N and -1 < ay < N and not visited[ay][ax] and minval <= height[ay][ax] <= maxval :
        visited[ay][ax] = True
        q.append((ax, ay))
        if maps[ay][ax] == 'K' :
          cnt += 1
    if cnt == H :
      return True
  return False

def two_pointer() :
  l, r = 0, 0
  ans = MAX+1
  while l < len(min_range) and r < len(max_range) :
    if bfs(min_range[l], max_range[r]) :
      ans = min(ans, max_range[r] - min_range[l])
      l += 1
    else :
      r += 1
  print(ans)

two_pointer()

풀이 완료!