백준2146 - 다리 만들기

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

2146번: 다리 만들기

bfs를 이용하여 푼 문제이다. 좌표를 입력받아서 영토를 구분하고 바다인 곳에 다리를 놓아 서로 다른 아무 영토나 최소 거리로 만나게 만들면 되는 문제다.

 

영토를 구분하는 방법은 bfs를 이용하여 영토인 지점에서 인접한 4방향으로 탐색을 한다. bfs를 진행할 때 현재 찾은 몇번째 영토인지 표시를 해주어 다리를 놓을 때 서로 다른 영토인 것을 알게 만든다.

 

다리를 놓는 방법은 바다인 지점에서 인접한 4방향으로 영토가 있는지 확인하고 영토와 맞닿은 부분이 있다면 다리를 놓는 작업을 시작한다. 마찬가지로 bfs를 이용하여 탐색하고 출발한 영토와 다른 영토를 만나면 그곳에서 탐색을 종료한다. 각각의 테스트 케이스마다 만들어진 다리의 갯수를 비교하여 최소값을 찾는다.

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 102
using namespace std;

//좌표(x, y), 현재 건설한 다리의 갯수는 z
class Point {
public:
	int x, y, z; //
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

int mat[MAX][MAX]; //좌표정보
bool mat_visit[MAX][MAX] = { false, }; //영토 방문 여부
int N; //좌표크기
int cnt = 1; //몇번째 섬인지 표시

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//섬에 출발점, 섬에 종착점
int start = 0;
int stop = 0;

int ans = 987654321; //답
int res = 0; //각 테스트 케이스마다 최소 다리 길이

//영토를 만드는 과정
void find_territory(int x, int y, int z) {
	queue<pair<int, int>> q; //영토가 될 곳을 담을 공간

	//첫번째 시작 영토를 넣고 그 부분의 좌표 정보를 현재까지 찾은 영토의 순서로 넣는다.
	q.push(pair<int, int>(x, y));
	mat[x][y] = z;
	mat_visit[x][y] = true;

	while (!q.empty()) {
		//맨 앞에 좌표정보 추출하고 삭제
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) { //상하좌우 이동
			int nx = x + dx[i];
			int ny = y + dy[i];

			//좌표가 유효범위이고 방문하지 않은 공간이며 영토이면
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && !mat_visit[nx][ny] && mat[nx][ny] == 1) {
				mat[nx][ny] = z; //현재 이동하려는 곳에 좌표 정보를 현재까지 찾은 영토의 순서로 넣는다.
				q.push(pair<int, int>(nx, ny)); //현재 이동하려는 곳을 큐에 삽입
				mat_visit[nx][ny] = true; //현재 이동하려는 곳을 방문처리
			}
		}
	}
}

//다리를 놓는 과정
void bridge(int x, int y, int z, int k) {
	queue<Point> q; //좌표에 대한 정보를 담는 공간
	bool bridge_visit[MAX][MAX] = { false }; //다리를 놓기 위한 공간에 방문정보

	q.push(Point(x, y, z)); //좌표의 위치와 비용을 삽입
	bridge_visit[x][y] = true; //좌표를 방문처리

	while (!q.empty()) {
		bool check = false; //영토를 찾았는지 못 찾았는지 체크하는 변수

		//맨 앞에 원소를 추출 후 삭제
		x = q.front().x;
		y = q.front().y;
		z = q.front().z;
		q.pop();

		for (int i = 0; i < 4; i++) { //상하좌우 이동
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//이동하려는 곳이 유효 범위이고 방문하지 않은 곳이면
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && !bridge_visit[nx][ny]) {
				if (mat[nx][ny] != 0 && mat[nx][ny] != k) { //출발한 영토와 다른 영토에 도착하면
					check = true; //영토를 찾음
					res = z; //다리의 갯수는 현재까지 건설한 다리의 갯수
					break; //탈출
				}
				else if (mat[nx][ny] == 0) { //바다이면
					q.push(Point(nx, ny, z + 1)); //다리의 갯수 증가시켜서 큐에 삽입
					bridge_visit[nx][ny] = true; //방문 처리
				}
				else if (mat[nx][ny] == k) { //출발한 영토와 같은 지점이면
					continue; //무시
				}
			}
		}

		if (check) { //영토를 찾았다면
			break; //탈출
		}
	}

	ans = min(ans, res); //최솟값 찾기
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mat[i][j];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (mat[i][j] == 1 && !mat_visit[i][j]) {
				find_territory(i, j, cnt); //영토를 만드는 과정
				cnt++; //찾은 영토의 갯수 증가
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (mat[i][j] == 0) { //바다이고
				if (mat[i - 1][j] != 0) { //위쪽이 육지면
					bridge(i, j, 1, mat[i - 1][j]); //위쪽 육지와 다른 나라를 찾는다.
				}
				if (mat[i + 1][j] != 0) { //아래쪽이 육지면
					bridge(i, j, 1, mat[i + 1][j]); //아래쪽 육지와 다른 나라를 찾는다.
				}
				if (mat[i][j - 1] != 0) { //왼쪽이 육지면
					bridge(i, j, 1, mat[i][j - 1]); //왼쪽 육지와 다른 나라를 찾는다.
				}
				if (mat[i][j + 1] != 0) { //오른쪽이 육지면
					bridge(i, j, 1, mat[i][j + 1]); //오른쪽 육지와 다른 나라를 찾는다.
				}
			}
		}
	}

	cout << ans;
}