[백준/BOJ] 백준 5873번 : Distant Pastures

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

5873번: Distant Pastures

 

각 위치를 노드로 다루어, 노드 번호[0 ~ n*n-1]를 부여하고, 이를 통해 플로이드 와샬로 최단 거리 비용을 구해서 문제를 해결했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n;
int a, b;
vector<string> board;
int dist[905][905]; //[노드번호1][노드번호2] = 노드번호1에서 노드번호2로 가는 최단 거리 비용 저장
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void pre() {

	for (int i = 0; i < 905; i++) {
		for (int j = 0; j < 905; j++) {
			if (i == j) {
				continue;
			}

			dist[i][j] = 987654321;
		}
	}

}

int solve() {

	//각 지점에서 4방향의 거리 비용 구하기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			pair<int, int> here = make_pair(i, j);
			int here_num = here.first * n + here.second;

			for (int dir = 0; dir < 4; dir++) {
				pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
				int there_num = there.first * n + there.second;

				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n) {
					if (board[here.first][here.second] == board[there.first][there.second]) { //같은 잔디일때
						dist[here_num][there_num] = a;
					}
					else { //다른 잔디일때
						dist[here_num][there_num] = b;
					}
				}
			}
		}
	}

	//플로이드 와샬을 통해 각 지점에서 최단 거리 비용 구하기
	for (int k = 0; k < n*n; k++) {
		for (int i = 0; i < n*n; i++) {
			for (int j = 0; j < n*n; j++) {

				if (dist[i][k] == 987654321 || dist[k][j] == 987654321) {
					continue;
				}

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

			}
		}
	}

	int ret = 0;
	for (int i = 0; i < n*n; i++) {
		for (int j = 0; j < n*n; j++) {
			if (dist[i][j] == 987654321) {
				continue;
			}
			ret = max(ret, dist[i][j]);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n >> a >> b;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		board.push_back(input);
	}

	int result = solve();
	cout << result;

	return 0;
}