[알고리즘] c++ cpp 다리 만들기

포인트

1. bfs를 2번을 진행을 하여 문제를 해결한다. 

2. (맵을 입력) -> (라벨링, 최소 거리를 찾는다.) -> (최솟값을 통해 최단거리를 구한다.)

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int n, answer;
int map[100][100];
bool visited[100][100];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

vector<pair<int, int>> vc;

void labeling(int a, int b, int label) {
	queue<pair<int, int>> q;
	q.push ({ a, b });
	visited[a][b] = 1;
	map[a][b] = label;

	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (!visited[nx][ny] && map[nx][ny] == -1) {
				q.push ({ nx, ny });
				visited[nx][ny] = 1;
				map[nx][ny] = label; // 전부 L로 라벨링
			}
		}
	}
}

int bfs(int num) {
	int result = 0;
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == num) {
				visited[i][j] = true;
				q.push(make_pair(i, j)); //1 인 것들을 전부 qd에 넣는다.
			}
		}
	}


	while (!q.empty()) {
		int len = q.size();
		while(len--){
			int x, y;
			tie(x, y) = q.front();
			q.pop();

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
				if (map[nx][ny] != 0 && map[nx][ny] != num) return result;

				if (map[nx][ny] == 0 && !visited[nx][ny]) {
					q.push ({ nx, ny });
					visited[nx][ny] = true;
				}
			}
		}
		result+=1;
	}
}


int main() {
	answer = 987654321;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) { //기본적로인 map 을 -1로 바꾼다.
				map[i][j] = -1;
				vc.push_back(make_pair(i, j));
			}
		}
	} // 값을 넣어준다.


	int label = 0;

	for(auto ele :vc) {
		if(!visited[ele.first][ele.second]) { //라벨링을 하는 작업
			labeling (ele.first, ele.second, ++label); 
		}
	}

	for (int i = 1; i < label; i++) {
		memset (visited, false, sizeof (visited));
		answer = min(answer, bfs(i));
	}
	cout << answer << '\n';


	return 0;
}