[白俊]2842号郵便配達員の韓尚徳

🔔 質問する

尚徳は山の斜面の村の郵便局で仕事を見つけた.村はNです.×N行列で表すことができます.行列によって区切られた地域ごとに、郵便局は「P」、家は「K」、牧場は「」です.そのうちの1つとして表すことができます.また、各地域の高さも知っています.
毎朝常徳は町のすべての家にメールを送ります.出前は町に郵便局「P」が1つしかないところから始まります.常徳は現在位置する格子と水平、垂直、対角線で隣接する格子に移動することができる.最後の手紙を送った後、郵便局に戻ります.
尚徳はこのように毎朝外食するのがどれだけ難しいか知りたい.尚徳配送時に訪問する車両の中で最も高い高さと最も低い高さの違いを疲労度と呼ぶ.このとき,最小の疲労度でプログラムを作成し,すべての家に配送する方法を尋ねる.
入力
1行目はNです.(2 ≤ N ≤ 50)
「次のN行には、村を代表する列があります.」「P」は1回のみ与えられ、「K」は少なくとも1回与えられる.
次のN行では、行列に分割された領域の高さが行列形式で与えられる.高さが1000000以下の自然数.
しゅつりょく
1行目に最小の疲労度を出力します.

🎯 解答方法

これはBFS+ダブルポインタの問題です.
村
海抜:地域の高さ
houses:Kの総数
疲労:すべての高さの種類
左、右:ダブルポインタ
px,py:開始点
答:最小の疲労度

始点、合計セット数、標高タイプの設定
1-1. 起点:郵便局の位置
1-2. 家屋総数:K個
1-3. 高さタイプ:すべての高さタイプ

すべての高さタイプを作成(疲労)

地区の高さ(高さ)を設定並べ替えて重複データ

を除去する.

BFSは、開始高さが最小(左)から最大(右)の高さの間にある場合にのみ起動します.BFSをブラウズすると、訪問するたびにKが1つ増えます.

すべての家屋を訪問する時、最小疲労度を求めます.

4でない場合は、最大(右)が残りの場合は、右が1増加します.

4、5全部でなければ終わりです.

最小疲労度を出力します.

上記の例1〜7番のアルゴリズムに従って動作すると、下図に示すように、7番のwhileゲートを迂回する.タイルは高さの昇順に並べられたタイルで、左、右はそれぞれそのタイルの要素を指します.

BFSブラウズは、開始点が最小～最大の範囲にある場合にのみ実行されます.BFSナビゲーションは合計5回実行され、下図はBFS実行時にナビゲートした経路を示しています.(3,4,5,6アルゴリズム)

🙄 見逃した場所

最小(左)から最大(右)の高さ範囲で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)