백준 2146 다리 만들기

www.acmicpc.net/problem/2146

2146번: 다리 만들기

백준 2146 다리 만들기

다리 만들기 문제는 그래프 문제이며 최소 거리를 구하기 때문에 BFS를 사용하면 된다. 나는 이문제를 해결하는데 조금 비효율 적으로 해결해서 시간이 생각보다 많이 나왔다. 다른 풀이를 참고하셨으면 좋겠다. 다른 풀이도 풀고 싶지만 지금 내가 너무 피곤해서 내일 일어나서 적어야 겠다. 

 

 

우선 단계적으로 

 

1단계 각 섬을 분리하기

 

여기서는 BFS난 DFS 둘 중 아무거나 사용해도 된다. 

 

2단계 각 섬에서 다른 섬으로 이동하는 길이를 BFS로 확인해주기 

BFS로 방문을 하며 섬에 방문했을 때 다른 섬일때만 이동할 수 있게 제한하기 

 

1섬 -> 2섬 일때만 인정

2섬 -> 2섬 일때는 방문 x

 

3단계 각 섬의 개수만큼의 배열에 다리 길이를 넣어주어 가장 작은 길이를 출력해준다.

 

해당 답의 경우 모든 정점에서 모든 길이를 다 확인해주어서 시간이 너무 오래걸려서 좋은 답은 아니다. 그래서 자고 일어나서 올바른 답을 추가해보겠습니다. 

 

#include <cstdio>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;

pair<int, int> map[102][102];
int xpos[4] = {0, -1, 0, 1}, ypos[4] = {1, 0, -1, 0};

int N, bridgeLength[102000], betweenLength[102][102];

int visited[102][102], bridgeVisited[102][102];

void bridgeBfs(int y, int x, int islandIndex);
void bfs(int y, int x, int islandIndex){
	
	queue<pair<int, int> > qu;
	qu.push(make_pair(y, x));
	map[y][x].second = islandIndex;
	visited[y][x] = 1;

	while(!qu.empty()){
		pair<int, int> now = qu.front();
		qu.pop();
		for(int i = 0; i < 4; i++){
			int nextY = now.first + ypos[i];
			int nextX = now.second + xpos[i];
			if(map[nextY][nextX].first == 1 && visited[nextY][nextX] == 0 && nextY >= 1 && nextX >= 1 && nextY <= N && nextX <= N){
				visited[nextY][nextX] = 1;
				map[nextY][nextX].second = islandIndex;
				qu.push(make_pair(nextY, nextX));
			}
		}
	}

}

int main(){
	scanf("%d", &N);
	memset(bridgeLength, 987654, sizeof(bridgeLength));
	memset(betweenLength, 987654, sizeof(betweenLength));
	
	int initValue = betweenLength[0][0];

	for(int y = 1; y <= N; y++){
		for(int x = 1; x <= N; x++){
			scanf("%d", &map[y][x].first);
		}
	}

	int islandIndex = 1;
	for(int y = 1; y <= N; y++){
		for(int x = 1; x <= N; x++){
			if(visited[y][x] == 0 && map[y][x].first == 1){
				bfs(y, x, islandIndex);
				islandIndex++;
			}
		}
	}

	for(int y = 1; y <= N; y++){
		for(int x = 1; x <= N; x++){
			if(map[y][x].first == 1){
				memset(betweenLength, 987654, sizeof(betweenLength));

				betweenLength[y][x] = 0;
				bridgeBfs(y, x, map[y][x].second);
			}
		}
	}
	
	

	int minValue = 987654321;
	for(int i = 1; i < islandIndex; i++){
		if(minValue > bridgeLength[i])
			minValue = bridgeLength[i];
	}
	printf("%d", minValue);
}


void bridgeBfs(int y, int x, int islandIndex){
	queue<pair<pair<int, int>, int> > qu;
	qu.push(make_pair(make_pair(y, x), betweenLength[y][x]));

	while(!qu.empty()){
		pair<pair<int, int>, int > now = qu.front();
		qu.pop();
		for(int i = 0; i < 4; i++){
			int nextY = now.first.first + ypos[i];
			int nextX = now.first.second + xpos[i];
			int nowCost = now.second;
			if(map[nextY][nextX].first == 0 && betweenLength[nextY][nextX] > nowCost + 1
				&& nextY >= 1 && nextX >= 1 && nextY <= N && nextX <= N){
				betweenLength[nextY][nextX] = nowCost + 1;
				qu.push(make_pair(make_pair(nextY, nextX), nowCost + 1));
			}else if(map[nextY][nextX].second != 0 && map[nextY][nextX].second != islandIndex && nextY >= 1 && nextX >= 1 && nextY <= N && nextX <= N){
				betweenLength[nextY][nextX] = min(nowCost, betweenLength[nextY][nextX]);
				bridgeLength[map[nextY][nextX].second] = min(nowCost, bridgeLength[map[nextY][nextX].second]);
				bridgeLength[islandIndex] = min(nowCost, bridgeLength[islandIndex]);
			}
		}
	}
}