백준 2146번: 다리 만들기

[문제 링크]

2146번: 다리 만들기

---

너비 우선 탐색을 활용하는 문제였다.

알고리즘은 다음과 같다.

 

1) 입력받은 배열에서 하나로 연결된 섬들을 1이 아닌 다른 숫자로 바꿔준다.

 

2) 배열의 모든 원소를 탐색하면서 0이 아닌 좌표를 발견하면 이 좌표를 시작점으로 하는 너비 우선 탐색을 수행한다.

 

3) 현재 좌표의 동서남북 방향에서 값이 0인 좌표와 (현재까지 놓은 다리 길이 + 1)을 큐에 담는다.

만약 현재 좌표에서 인접한 곳에 다른 섬이 존재한다면 두 섬이 연결된 것이므로 현재까지 놓은 다리 길이를 반환한다.

 

4) 0이 아닌 모든 좌표에 대해 너비 우선 탐색을 수행하면서 반환된 다리 길이 중 가장 작은 값을 결과로 출력한다.

---

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N;
int board[100][100];
bool visited[100][100];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(Pos start, int type) {
	queue<pair<Pos, int>> q;
	q.push({ start, 0 });
	visited[start.y][start.x] = true;

	while (!q.empty()) {
		Pos here = q.front().first;
		int isLen = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };

			if (there.y >= 0 && there.y < N && there.x >= 0 && there.x < N) {
				int nextType = board[there.y][there.x];

				if (!visited[there.y][there.x] && nextType == 0) {
					visited[there.y][there.x] = true;
					q.push({ there, isLen + 1 });
				}
				else if (nextType != 0 && nextType != type)
					return isLen;
			}
		}
	}

	return INF;
}

void divide_Island(Pos start, int type) {
	queue<Pos> q;
	q.push(start);
	board[start.y][start.x] = type;

	while (!q.empty()) {
		Pos here = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			
			if(there.y >= 0 && there.y < N && there.x >= 0 && there.x < N)
				if (board[there.y][there.x] == 1) {
					board[there.y][there.x] = type;
					q.push(there);
				}
		}
	}
}

int main(void) {
	cin >> N;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	int type = 2;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (board[i][j] == 1) {
				divide_Island({ i,j }, type);
				type++;
			}

	int result = INF;
	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (board[i][j] != 0) {
				memset(visited, false, sizeof(visited));
				result = min(result, bfs({ i,j }, board[i][j]));
			}
		}

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day