백준 #31849 편세권

문제 링크

[31849 편세권]

문제 설명

월세방과 편의점의 위치들이 주어졌을때 월세방과 편의점 사이의 거리 곱하기 월세가 가장 작은 월세방을 찾는 문제

코드

import sys
input = sys.stdin.readline
from collections import deque


def solve(q):
    while q:
        r, c = q.popleft()
        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue
            if visited[nr][nc] == -1:
                visited[nr][nc] = visited[r][c] + 1
                q.append((nr, nc))

N, M, R, C = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(R)]
visited = [[-1] * M for _ in range(N)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
q = deque()
for _ in range(C):
    x, y = map(int, input().split())
    q.append((x - 1, y - 1))
    visited[x - 1][y - 1] = 0

solve(q)
min_score = float("inf")
for i in range(R):
    x, y, p = room[i]
    dist = visited[x - 1][y - 1]
    score = dist * p
    if min_score > score:
        min_score = score

print(min_score)

풀이

예전에 풀었던 토마토?랑 비슷한 문제이다. BFS문제인데 편의점의 위치를 미리 큐에 담아두고 동시에 퍼뜨려서 편의점으로부터 각 격자점까지의 거리를 표시하면 각 격자점으로부터 편의점까지 가장 가까운 거리가 표시된다. 격자점중에는 월세방도 있으니깐 월세방을 전부 체크하면서 편세권 점수를 계산해서 낮은 점수를 찾으면된다. 처음에는 편의점 하나하나 전부 BFS를 돌려서 시간초과가 계속 났었다. 골드5라서 만만하게 봤는데 은근 시간이 걸렸던 문제!