[BOJ] 2842 집배원 한상덕 python

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

2842번: 집배원 한상덕

1. 풀이

사용한 알고리즘은 bfs + 투포인터 이다. 먼저 주어진 지역의 고도 행렬을 중복이 없은 1차원 리스트로 만들어 준 후에 오름차순 정렬해준다. 이 리스트를 heights라고 하겠다. 이후에 초기값이 0인 left, right를 지정해놓고 포인터 값을 변경해가며 heights를 이용해 bfs를 시행하면 되는데 구체적인 로직은 다음과 같다.

 

1. heights[left:right]를 sub_heights라고 하고 sub_heights안에 있는 값 만으로 집을 모두 탐색할 수 있는지 확인한다.(bfs)
   • 새롭게 방문한 점을 (nr, nc)라고 할 때  sub_heights[0] <= HEIGHT[nr][nc] <= sub_heights[-1]이면 방문 가능
   • 여기서 HEIGHT는 지역의 고도 행렬  HEIGHT[nr][nc] => nr, nc에서 고도 값
2. 탐색 결과를 바탕으로 아래 사항를 수행한다.
   1. 만약 탐색할 수 없다면 right를 1증가 시키고 현재 정답과 sub_heights의 최대값과 최소값 차이를 비교해 정답을 갱신해준다.
   2. 만약 탐색할 수 있다면 left를 1증가 시킨다.(최대값과 최소값의 차이를 줄이기 위해)
3. right가 heights의 길이와 같아지면 반복문을 종료한다.

코드는 아래와 같다.

import sys
from collections import deque

def solution():
    input = sys.stdin.readline
    N = int(input()) 
    board = [list(map(str, input())) for _ in range(N)] #상덕이가 움직일 곳
    HEIGHT = [list(map(int, input().split())) for _ in range(N)] # 지역의 고도
    moves = [(0,1),(1,0),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
    houses = 0
    heights = []
    
    #시작위치와 집의 개수를 파악한다.
    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
            heights.append(HEIGHT[i][j])
   	# 중복이 없는 정렬된 1차원 배열
    heights = sorted(set(heights))
    left, right = 0, 0
    ans = float('inf')
    while left < len(heights):
	    #left, right를 움직이면서 탐색해준다.
        visit = [[False] * N for _ in range(N)] 
        q = deque()
        #시작점의 고도가 범위안에 들어와야한다.
        if heights[left] <= HEIGHT[sx][sy] <= heights[right]: 
            visit[sx][sy] = True
            q.append((sx, sy))

        cnt = 0 # 방문한 집의 개수
        while q:
            r, c = q.popleft()
            for dr, dc in moves:
                nr, nc = r + dr, c + dc
                if 0 > nr or nr >= N or 0 > nc or nc >= N:
                    continue
                # 새로 방문한 곳의 고도가 범위안에 포함되면
                if not visit[nr][nc] and heights[left] <= HEIGHT[nr][nc] <= heights[right]: 
                    if board[nr][nc] == 'K': cnt += 1
                    visit[nr][nc] = True
                    q.append((nr, nc))
                    

        if cnt == houses: # 집을 모두 방문했다면
            ans = min(ans, heights[right] - heights[left]) #정답 갱신
            left += 1 # 포인터를 왼쪽으로 옮겨서 더 고도의 범위를 좁혀준다.(탐색가능한 최소값을 찾을 것)
        elif right + 1 < len(heights): # 아직 남아있는 최대 고도가 있을 때
            right += 1 # 포인터를 오른쪽으로 옮겨서 더 고도의 범위를 넓혀준다.
        else: # 방문 못햇다면
            break 
    print(ans)

solution()