[BAE/<JOON> 문제풀이] 2146. 다리 만들기

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

2146번: 다리 만들기

2146:: 다리 만들기

핵심::
BFS

풀이::
1. 섬을 찾고 번호 부여 -> 찾은 섬 부분을 모두 큐에 집어넣고 2번 탐색 시작

2. 섬 경계를 확장하며 서로 다른 번호를 가진 섬 경계가 맞닿는 경계 찾기

3. 최소값 초기화 

풀이 로직은 간단한데 코드가 좀 길다.

의견::
진짜 쉬워뵈는데 까다로움

 

코드::

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
	int x, y;
};

struct node2 {
	int in, c;
};

int mvx[4] = { 1, 0, -1, 0 };
int mvy[4] = { 0, 1, 0, -1 };

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1));

	int icnt = 2;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}

	queue<node> que;
	vector<vector<node2>> ch(n + 1, vector<node2>(n + 1));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == 1) {
				arr[i][j] = icnt;
				ch[i][j].in = icnt;
				ch[i][j].c = 0;
				que.push({ i, j });
				queue<node> q;
				q.push({ i, j });
				while (!q.empty()) {
					auto cur = q.front(); q.pop();
					for (int i = 0; i < 4; i++) {
						int mx = cur.x + mvx[i];
						int my = cur.y + mvy[i];
						if (mx < 1 || mx > n || my < 1 || my > n) continue;
						if (arr[mx][my] != 1) continue;
						arr[mx][my] = icnt;
						ch[mx][my].in = icnt;
						ch[mx][my].c = 0;
						q.push({ mx, my });
						que.push({ mx, my });
					}
				}
				icnt++;
			}
		}
	}	

	int mn = 2100000000;
	while (!que.empty()) {
		auto cur = que.front(); que.pop();
		for (int i = 0; i < 4; i++) {
			int mx = cur.x + mvx[i];
			int my = cur.y + mvy[i];
			if (mx < 1 || mx > n || my < 1 || my > n) continue;
			if (ch[mx][my].in != ch[cur.x][cur.y].in && ch[mx][my].in != 0) {					
				int s = ch[mx][my].c + ch[cur.x][cur.y].c;
				mn = mn < s ? mn : s;				
			}
			if (arr[mx][my] != 0) continue;		
			arr[mx][my] = -1;
			ch[mx][my].in = ch[cur.x][cur.y].in;
			ch[mx][my].c = ch[cur.x][cur.y].c + 1;
			que.push({ mx, my });
		}
	}	

	cout << mn;

	return 0;
}