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

www.acmicpc.net/problem/2842

2842번: 집배원 한상덕

 

문제풀이

N : 입력값

board : 입력값(마을을 나타내는 행렬)

tiredness : 입력값(지역의 고도)

houses : 전체 K의 개수

fatigue : 중복 제거 후 정렬된 tiredness

left, right : 투 포인터

ans : 결과값(가장 작은 피로도)

 

BFS와 투 포인터(Two-Pointer) 를 결합한 문제이다. 굉장히 까다롭고 어려운 문제라고 생각한다...

핵심은 입력받은 고도에 대해서 투 포인터를 위해 중복을 제거하고 정렬하는 것이다.

이후 최대 고도와 최소 고도를 변경해가며 모든 집을 방문하였을 때  두 고도 간 최소 차이를 구해야 한다.

 

1. 입력받은 고도(tiredness) 에 대해서 정렬 및 set을 통해 중복 제거 => fatigue

 

2. 투 포인터를 통해 최대 고도와 최소 고도를 설정한다.

- 시작점의 고도가 최대 고도와 최소 고도 사이일 경우에만 BFS를 시작한다.

- BFS를 통해 탐색하게 될 곳의 고도 또한 최대 고도와 최소 고도 사이일 경우에만 탐색한다.

- 방문할 곳이 집일 경우 K 증가

 

3. BFS 탐색 후 방문한 집의 개수(K)가 전체 집의 개수(houses)와 동일할 경우에만 최소 피로도를 구한다.

- 피로도를 갱신하였을 경우, 갱신한 피로도보다 더 적은 피로도로 모든 집을 탐색할 수 있는지 확인하기 위해 최소 고도(left) 를 1 증가한다. => 최소고도를 높일수록 피로도는 감소한다.

 

4. 3이 아닐 경우에, 남아있는 최대 고도가 있을 경우 right를 1 증가한다.

 

5. 3, 4 모두 아닐 경우 종료한다. => 최소 피로도 출력

 

코드

import sys
from collections import deque

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

if __name__ == '__main__':
    N = int(input())
    board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]
    tiredness = [[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':
                sx, sy = i, j
            if board[i][j] == 'K':
                houses += 1
            fatigue.append(tiredness[i][j])
    # 고도 set 및 정렬 필요 => 정렬 : 투 포인터 set : 중복된 고도 제거
    fatigue = sorted(set(fatigue))
    left, right = 0, 0
    ans = sys.maxsize
    while left < len(fatigue):
        visit = [[False] * N for _ in range(N)] # left나 right를 움직일 때마다 visit 초기화 필요
        tired = tiredness[sx][sy] # 시작점 피로도
        q = deque()
        K = 0 # 방문한 집의 개수
        if fatigue[left] <= tired <= fatigue[right]: # 시작점 피로도가 투 포인터 사이의 피로도에 속할 경우에만 BFS시작
            visit[sx][sy] = True
            q.append((sx, sy))
        while q:
            x, y = q.popleft()
            for k in range(8):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < N:
                    if visit[nx][ny]: continue
                    tired = tiredness[nx][ny]
                    # 현재 피로도가 left, right 사이 피로도일 경우에만 추가로 탐색
                    if fatigue[left] <= tired <= fatigue[right]:
                        visit[nx][ny] = True
                        q.append((nx, ny))
                        if board[nx][ny] == 'K': K += 1
        if K == houses: # 집을 모두 방문했을 때
            ans = min(ans, fatigue[right] - fatigue[left]) # 최소 피로도 구하기
            left += 1 # 최소 높이 증가
        elif right + 1 < len(fatigue): # 아직 남아있는 최대 고도가 있을 때
            right += 1 # 최대 고도 증가
        else: break # 집을 모두 방문하지 않았는데 최대 고도일 경우 종료
    print(ans)

 

결과

 

위 풀이는 'jaimemin' 님의 C++ 풀이를 참고한 코드입니다.

jaimemin.tistory.com/1279

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!