[BOJ/백준] 31849 - 편세권

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

---

자취방을 기준으로 먼저 생각하기보다 편의점을 기준으로 생각하기

편의점부터 모든 점의 거리를 한번에 BFS로 계산하기

---

---

• 제목

편세권

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

왕복 4시간 통학에 지친 현성이는 자취방을 구하려고 한다.

현성이가 방을 고르는 기준은 월세와 편의점까지의 거리뿐이다. 가장 마음에 드는 방을 구하기 위해 현성이는 지도 위의 모든 방에 편세권 점수를 매겨 그 중 편세권 점수가 가장 낮은 집을 고르려고 한다. 편세권 점수의 계산 방식은 다음과 같다.

편세권 점수 = (방에서 가장 가까운 편의점까지의 거리 × 월세)

현성이가 보고 있는 지도는 N X M 크기의 격자로 이루어져 있다. 지도의 x행 y열에 있는 칸의 위치를 (x,y)로 나타내자. 방의 위치가 (a,b), 편의점의 위치가 (c,d)일 때 방에서 편의점까지의 거리는 |a-c|+|b-d| 로 계산한다.

현성이는 가장 낮은 편세권 점수를 가진 방을 골랐다. 이 방의 편세권 점수는 몇 점일까?

---

• 입력

첫 번째 줄에 지도의 크기를 나타내는 정수 N과 M, 방의 개수 R, 편의점의 개수 C가 공백으로 구분되어 주어진다.

두 번째 줄부터 R개의 줄에 걸쳐 방의 정보를 나타내는 세 정수 ai, bi, pi가 공백으로 구분되어 주어진다. 이는 i번째 방이 (ai, bi)에 있으며, 월세가 pi임을 나타낸다.
 
R+2번째 줄부터 C개의 줄에 걸쳐 편의점의 정보를 나타내는 두 개의 정수 cj, dj가 공백으로 구분되어 주어진다. 이는 j번째 편의점이 (cj, dj)에 있음을 나타낸다.

모든 방과 편의점의 위치는 서로 다르다. 즉, 한 위치에는 최대 한 개의 방이나 한 개의 편의점만이 있을 수 있다.

---

• 출력

첫째 줄에 현성이가 고른 방의 편세권 점수를 출력한다.

---

• 제한

 2 ≤ N ≤ 1000
2 ≤ M ≤ 1000
2 ≤ R+C ≤ min(NM, 5 X 10^5)
1 ≤ ai, cj ≤ N
 1 ≤ bi, dj ≤ M
 1 ≤ pi ≤ 100
방과 편의점은 각각 1개 이상 존재한다.

---

 

예제 입력1	예제 출력1
5 5 2 1 1 1 2 4 5 3 4 3	6

 

예제 입력2	예제 출력2
5 5 2 3 1 1 2 4 5 3 2 2 2 4 4 3	4

 

---

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());

		ArrayList<int[]> rooms = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken());
			rooms.add(new int[] {x, y, c});
		}

		int[][] dist = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				dist[i][j] = Integer.MAX_VALUE;
			}
		}

		Queue<int[]> queue = new ArrayDeque<>();
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			dist[x][y] = 0;
			queue.add(new int[] {x, y, 0});
		}

		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, 1, -1};
		while (!queue.isEmpty()) {
			int[] curr = queue.poll();
			int x = curr[0];
			int y = curr[1];
			int d = curr[2];
			for (int k = 0; k < 4; k++) {
				int tx = x + dx[k];
				int ty = y + dy[k];
				if (tx < 0 || ty < 0 || tx >= N || ty >= M) {
					continue;
				}
				if (dist[tx][ty] <= d + 1) {
					continue;
				}
				dist[tx][ty] = d + 1;
				queue.add(new int[] {tx, ty, d + 1});
			}
		}

		int answer = Integer.MAX_VALUE;
		for (int[] room : rooms) {
			answer = Math.min(answer, room[2] * dist[room[0]][room[1]]);
		}
		System.out.println(answer);
	}
}