[BOJ/Gold 5] 백준 31849 편세권(C++, Java)

문제 링크

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

 

문제

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

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

 

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

 

현성이가 보고 있는 지도는 𝑁×𝑀 크기의 격자로 이루어져 있다. 지도의 𝑥행 𝑦열에 있는 칸의 위치를 (𝑥, 𝑦)로 나타내자. 방의 위치가 (𝑎, 𝑏), 편의점의 위치가 (𝑐, 𝑑)일 때 방에서 편의점까지의 거리는 |𝑎 − 𝑐| + |𝑏 − 𝑑| 로 계산한다.

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

 

입력

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

두 번째 줄부터 𝑅개의 줄에 걸쳐 방의 정보를 나타내는 세 정수 𝑎𝑖, 𝑏𝑖, 𝑝𝑖가 공백으로 구분되어 주어진다. 이는 𝑖번째 방이 (𝑎𝑖, 𝑏𝑖)에 있으며, 월세가 𝑝𝑖임을 나타낸다.

 𝑅 + 2번째 줄부터 𝐶개의 줄에 걸쳐 편의점의 정보를 나타내는 두 개의 정수 𝑐𝑗, 𝑑𝑗가 공백으로 구분되어 주어진다. 이는 𝑗번째 편의점이 (𝑐𝑗, 𝑑𝑗)에 있음을 나타낸다.

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

 

출력

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

 

제한

•  2 ≤ 𝑁 ≤ 1,000
•  2 ≤ 𝑀 ≤ 1,000
•  2 ≤ 𝑅 + 𝐶 ≤ min(𝑁𝑀, 5×10^5)
•  1 ≤ 𝑎𝑖, 𝑐𝑗 ≤ 𝑁
•  1 ≤ 𝑏𝑖, 𝑑𝑗 ≤ 𝑀
•  1 ≤ 𝑝𝑖 ≤ 100
• 방과 편의점은 각각 1개 이상 존재한다.

 

예제 입력 1

5 5 2 1
1 1 2
4 5 3
4 3

예제 출력 1

6

예제 입력 2

5 5 2 3
1 1 2
4 5 3
2 2
2 4
4 3

예제 출력 2

4

 

힌트

 

예제 1번의 경우 월세가 3이고, 편의점까지의 거리가 2인 자취방의 편세권 점수가 6으로 가장 낮다.

 

 

예제 2번의 경우 월세가 2이고, 편의점까지의 거리가 2인 자취방의 편세권 점수가 4로 가장 낮다. 

 

알고리즘 분류

• 그래프 탐색

 

풀이

모든 편의점을 기준으로, BFS로 상하좌우를 탐색하며 가장 먼저 만나는 집이 존재하면 집과의 거리와 해당 집의 월세의 곱인 편세권 점수의 최소값을 구한다.

 

코드

C++

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct CONVENIENCE {
    int C, D;
};

int N, M, R, C;
vector<CONVENIENCE> Conveniences;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = INF;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Visited[i][j] = false;
        }
    }
}

void input() {
    cin >> N >> M >> R >> C;
    for (int i = 0; i < R; i++) {
        int a, b, p;
        cin >> a >> b >> p;
        MAP[a][b] = p;
    }
    for (int i = 0; i < C; i++) {
        int c, d;
        cin >> c >> d;
        Conveniences.push_back({ c,d });
    }
}

void bfs() {
    queue<pair<pair<int, int>, int> > Q;
    for (int i = 0; i < C; i++) {
        int c = Conveniences[i].C;
        int d = Conveniences[i].D;
        Q.push(make_pair(make_pair(c, d), 0));
        Visited[c][d] = true;
    }

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowT = Q.front().second;
        Q.pop();

        if (MAP[NowY][NowX] > 0) {
            Answer = min(Answer, NowT * MAP[NowY][NowX]);
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY > 0) && (NextY <= N) && (NextX > 0) && (NextX <= M) && !Visited[NextY][NextX]) {
                Q.push(make_pair(make_pair(NextY, NextX), NowT + 1));
                Visited[NextY][NextX] = true;
            }
        }
    };
}

void settings() {
    bfs();
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}​

 

Java

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

public class Main {
	
	static int[][] MAP = new int[1001][1001];
	static int[] MoveY = { -1,0,1,0 };
	static int[] MoveX = { 0,-1,0,1 };
	static int Answer = 1000000000;
	
	public static class Convenience {
		int c, d;
		
		public Convenience(int c, int d) {
			this.c = c;
			this.d = d;
		}
	}
	
	public static class ConvenienceInfo {
		int y, x, t;
		
		public ConvenienceInfo(int y, int x, int t) {
			this.y = y;
			this.x = x;
			this.t = t;
		}
	}
	
	public static void find_Answer() {
		System.out.println(Answer);
	}
	
	public static void settings(int N, int M, int C, Convenience[] convenience) {
		boolean[][] Visited = new boolean[1001][1001];
		Queue<ConvenienceInfo> que = new LinkedList<ConvenienceInfo>();
		for (int i = 0; i < C; i++) {
			int c = convenience[i].c;
			int d = convenience[i].d;
			que.add(new ConvenienceInfo(c, d, 0));
			Visited[c][d] = true; 
		}
		
		while (!que.isEmpty()) {
			ConvenienceInfo nowConvenienceInfo = que.poll();
			int NowY = nowConvenienceInfo.y;
			int NowX = nowConvenienceInfo.x;
			int NowT = nowConvenienceInfo.t;
			
			if (MAP[NowY][NowX] > 0) {
				Answer = Math.min(Answer, MAP[NowY][NowX] * NowT);
			}
			
			for (int i = 0; i < 4; i++) {
				int NextY = NowY + MoveY[i];
				int NextX = NowX + MoveX[i];
				if ((NextY > 0) && (NextY <= N) && (NextX > 0) && (NextX <= M) && !Visited[NextY][NextX]) {
					que.add(new ConvenienceInfo(NextY, NextX, NowT + 1));
					Visited[NextY][NextX] = true; 
				}
			}
		};
		
		
		find_Answer();
	}
	
	public static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int M = Integer.parseInt(input[1]);
		int R = Integer.parseInt(input[2]);
		int C = Integer.parseInt(input[3]);
		for (int i = 0; i < R; i++) {
			String[] A = br.readLine().split(" ");
			int a = Integer.parseInt(A[0]);
			int b = Integer.parseInt(A[1]);
			int p = Integer.parseInt(A[2]);
			MAP[a][b] = p; 
		}
		Convenience[] convenience = new Convenience[C];
		for (int i = 0; i < C; i++) {
			String[] A = br.readLine().split(" ");
			int c = Integer.parseInt(A[0]);
			int d = Integer.parseInt(A[1]);
			convenience[i] = new Convenience(c, d); 
		}
		settings(N, M, C, convenience);
	}

	public static void main(String[] args) throws IOException {
		input();
	}

}