편세권

문제 링크

편세권

아이디어

1. 제약조건을 읽어 본 결과, 모든 가게에 대해서 거리 계산을 하는 브루트포스 방식은 도입이 어렵다고 생각

   • \[2 \leq N, M \leq 10^4\]
   • \[2 \leq R + C \leq min(NM, 5 \times 10^5)\]

   브루트 포스 방식으로 모든 편의점에 대해서 완전 탐색하는 방식은 \(R \times E\)

   • \(E\) 는 \(\textrm{가게} \rightarrow \textrm{편의점}\) 사이에 존재할 수 있는 모든 edge의 수 \(= C\)
   • \(R + C \leq min(NM, 5 \times 10^5)\) 에 따라서, \(R, C \leq 5 \times 10^5\)
   • \[R \times C = 25 \times 10^{10}\]
2. \[\textrm{방} \rightarrow \textrm{편의점} = \textrm{편의점} \rightarrow \textrm{방}\]
   • 양방향 edge가 거리에 영향을 주는 요소는 없음

3. 월세는 가게마다 고정적이므로, 편의점에서 가게까지의 거리가 편세권 점수에 영향을 미친다.

   • 모든 편의점에서 시작하여 가장 최단거리에 있는 가게를 선정하는 방식으로 최단 거리를 보장할 수 있음
   • 멘헤튼 거리의 계산법을 따르므로, BFS를 이용하여 마주치는 가게가 현재까지의 탐색에서 최단 거리임을 보장할 수 있음
   • BFS에 의해서 이전에 방문 처리가 된 가게는, 다른 편의점과 더 가까운 위치에 위치하는 것이 보장되므로 후보해에서 제외해도 무방하다.

시간 복잡도는 BFS탐색에 의해서 \(O(N \times M)\) 임이 보장된다. (하나의 노드를 최대 1번만 방문 가능하도록 설계하였기 때문)

소스코드

#include <bits/stdc++.h>
using namespace std;
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int N, M, R, C, board[1001][1001];
bool visited[1001][1001];
int main(void) {
    int ans = 0x3f3f3f3f;
    fill(&board[0][0], &board[1000][1001], -1);
    cin >> N >> M >> R >> C;
    
    // board : [1][1] ~ [N][M]
    for (int i = 0; i < R; i++) {
        int a, b, p;
        cin >> a >> b >> p;
        board[a][b] = p;
    }

    // {r, c, ac_dist}
    queue<pair<int,int>> q;
    for (int i = 0; i < C; i++) {
        int c, d;
        cin >> c >> d;
        q.emplace(c, d);
    }

    int dist = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [r, c] = q.front(); q.pop();
            for (int d = 0; d < 4; d++) {
                int nr = r + dir[d][0], nc = c + dir[d][1];
                if (1 <= nr && nr <= N && 1 <= nc && nc <= M && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    if (board[nr][nc] != -1) {
                        ans = min(ans, dist * board[nr][nc]);
                    }
                    q.emplace(nr, nc);
                }
            }
        }
        dist++;
    }
    cout << ans;

    return 0;
}