백준 31849 - 편세권(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31849

 

BFS를 이용한 문제입니다.

 

편의점의 위치와 자취방의 위치가 주어졌을 때, 편의점과 자취방의 가장 가까운 거리를 구하는 문제입니다.

 

거리를 구하는 수식 -> 자취방에서 편의점까지의 거리 * 월세 입니다.

 

문제를 풀기 위해서는 모든 자취방과 편의점 사이의 거리를 구하면 된다라는 생각을 할 수 있습니다.

하지만, 방과 편의점의 최대 개수가 5*10^5 이기에 모든 경우를 탐색한다면 시간 초과가 생길 것입니다.

 

한번 생각을 해보면, 어떤 편의점에서 출발을 하든 어떤 자취방에 먼저 도착하는 곳이 있다면 해당 편의점이 해당 자취방과 가장 가까운 곳이라는 것이 됩니다.

 

그렇다면, 모든 편의점에서 동시에 출발해서 각각의 자취방까지 도달하는 것을 구현해주면 됩니다.

어떤 편의점에서 도착한 자취방이 있는데, 이전에 방문됐던 자취방이라면 해당 경우를 가장 가까운 거리가 아니라는 의미가 되니 확인을 할 필요도 없어집니다.

-> 이는 BFS로 구현할 수 있습니다.

 

 

따라서 BFS를 통해 각 편의점의 위치에서 동시에 출발하고 도착하는 자취방이 있다면 거리를 계산해 최솟값을 찾아주는 과정을 거쳐주면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;
int N, M, R, C;
int map[1001][1001];
int check[1001][1001];
vector<pair<pair<int, int>, int>> house;
queue<pair<pair<int, int>, pair<int, int>>> q;
int dx[4] = { 1 , 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ans = INT_MAX;

void bfs() {
	while (!q.empty()) {
		int combi_x = q.front().first.first;
		int combi_y = q.front().first.second;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (check[xx][yy] != 0) continue;
				if (map[xx][yy] != 0) {
					int Dis = (abs(combi_x - xx) + abs(combi_y - yy)) * house[map[xx][yy] - 1].second;
					ans = min(ans, Dis);
				}
				check[xx][yy] = 1;
				q.push({ {combi_x, combi_y}, {xx, yy} });
			}
		}
	}
}

void solve() {
	bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> R >> C;
	int cnt = 1;
	for (int i = 1; i <= R; i++) {
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		house.push_back({ {x, y}, cost });
		map[x][y] = cnt++;
	}
	for (int i = 1; i <= C; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		q.push({ {x, y}, {x, y} });
		check[x][y] = 1;
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.