백준 17472 다리만들기2 C 풀이 - MST, DFS

바다와 섬이 그려져있는 지도에 다리를 만들되, 다리를 최소한의 길이로 만들고 싶다.

 

조건은 다음과 같다.

1. 다리의 길이는 1보다 길어야한다.

2. 섬이 모두 연결되어야 한다. (연결 안될 경우 -1출력)

3. 다리는 일직선으로만 만들 수 있다.

4. 다리 양끝에 다리 방향으로 섬이 연결되어야 한다.(옆 방향에 붙는 것 안됨)

5. 다리는 교차할 수 있지만, 길이는 중복해서 센다. 가령 길이 3인 도로가 + 형태로 겹쳐있어도 길이는 6이다.

 

접근 방식은 다음과 같다.

1. 섬마다 번호를 매긴다.

2. 섬마다 만들 수 있는 다리를 모두 만들어 보고, 연결할 수 있는 섬과 그 때의 다리의 길이를 저장한다.

3. 최소 값으로 섬들을 연결시킨다.

4. 섬들이 모두 연결되어 있는지를 확인한다.

 

문제를 풀면서 고생한 점은 다음과 같다.

1. 최소값으로 다리를 연결시키는데 DFS,BFS방식으로 구현하는데 애를 먹어서 결국 최소 스패닝 트리(MST)로 구현했다.

2. Minimum Spanning Tree로 구현하려니 Join 과 Find 를 기억하는데 조금 걸렸다.

 

Find함수는 자신과 연결된 노드 중 가장 작은 번호를 가지는 노드를 출력한다.

 

joint 함수는 두 노드를 join 시키는데, 항상 작은 값으로 join시키기 위해서 두 가지 케이스로 나눠서 진행했다.

두 개의 그룹이 join 할 때는 더 작은 노드를 가지는 그룹이 흡수하는 식으로 설정했다.

가령 1 - 2 - 3 이 연결된 그룹과 4 - 5 - 6 이 연결된 그룹을 합치면 모두 used배열 (연결된 노드 저장)에 모두

1 1 1 1 1 1 이 저장되도록 설계했다.

 

tree 함수는 길이 저장된 배열에서 최소 길이의 다리를 찾아내는 것을 시작으로, 시작섬(y)과 도착섬(x)를 구하여

두 개가 서로 연결되어 있지 않으면 그룹화한다.(joint) 

만약 모든 다리에 대해 수행해봤다면 종료한다.(min == INF ) 

사용한 다리는 끊긴 것으로 처리해준다.(Road[y][x] = INF, Road[x][y] = INF) 

여기서 연결이 가능할 경우, 다리의 길이를 기록해둔다.(ret += Road[y][x]);

 

Numbering 함수는 맵에 있는 섬을 찾아 번호를 매기는 작업을 한다.

 

makeRoad 함수는 섬마다 다리를 만들 수 있는지를 찾고, 다리를 만들 수 있다면 도착섬과 시작섬을 연결하고

그 때의 길이를 저장한다.

더 짧은 길이의 다리를 만들 수 있다면 갱신한다.

만약 길이가 1이라면 저장하지 않는다.

 

solve 함수에서는 전체 해결 과정이 들어있다. 

1. 섬에 번호를 매긴다.

2. 다리를 연결시킨다.

3. 트리를 만든다.

4. 답을 확인한다.

 

전체코드

#include <stdio.h>

#define INF 987654321
int N, M;
int Map[11][11];//인풋
int visited[11][11];//넘버링
int Road[11][11];//다리 연결된 최솟값
int used[11];//섬까지 최소 다리 
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int islandnum;//섬의 수
int ans;
//조건
//1.다리의 길이는 1이상
//2.섬이 모두 연결되어야함
//3. 교차가능
//4. 중간에 꺾이기 불가능
//5. 다리 끝에 (방향대로) 섬이 두 개 다 붙어있어함.
int find(int n) {
	if (used[n] == n) return n;
	return find(used[n]);
}
int joint(int a, int b) {
	if (find(a) < find(b)) {
		while (1) {
			int tmp = used[b];
			used[b] = find(a);
			if (tmp == b) break;
			b = tmp;
		}
	}
	else {
		while (1) {
			int tmp = used[a];
			used[a] = find(b);
			if (tmp == a) break;
			a = tmp;
		}
	}
	return 0;
}


int tree() {
	int ret = 0;
	for (int i = 1; i <= islandnum; i++) {
		used[i] = i;
	}

	while (1) {
		
		int y = 0, x = 0;
		int min = INF;
		for (int i = 1; i <= islandnum; i++) {
			for (int j = 1; j <= islandnum; j++) {
				if (min > Road[i][j]) {
					min = Road[i][j];
					y = i;
					x = j;
				}
			}
		}
		if (min == INF) break;
		if (find(x) == find(y)) {
			Road[y][x] = INF;
			Road[x][y] = INF;
			continue;
		}
		joint(x, y);
		ret += Road[y][x];
		Road[y][x] = INF;
		Road[x][y] = INF;
		
	}
	return ret;
}

void Numbering(int y, int x,int num) {

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
		if (Map[ny][nx] == 0) continue;
		if (visited[ny][nx]) continue;
		visited[ny][nx] = num;
		Numbering(ny, nx, num);
	}

}



void makeRoad() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j]) {
				int num = visited[i][j];
				for (int dir = 0; dir < 4; dir++) {
					int roadlen = 0;
					int ny = i+dy[dir];
					int nx = j+dx[dir];
					//연결
					while (1) {
						if (ny < 0 || ny >= N || nx < 0 || nx >= M) break;
						if (visited[ny][nx] == num) break;
						if (visited[ny][nx] == 0) {
							ny += dy[dir];
							nx += dx[dir];
							roadlen++;
						}
						else {
						//printf("i :  %d j : %d ny : %d nx : %d len %d\n", i, j, ny, nx,roadlen);
							int newIsland = visited[ny][nx];
							if (roadlen < 2) break;
							if (Road[num][newIsland] > roadlen) {
								Road[num][newIsland] = roadlen;
								Road[newIsland][num] = roadlen;
							}
							break;
						}
					}

				}
			}
		}
	}
}

int solve() {
	islandnum = 1;
	//섬에 번호 매기기 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j]) {
				if (visited[i][j]) continue;
				visited[i][j] = islandnum;
				Numbering(i, j, islandnum++);
			}
		}
	}

	islandnum--; //섬의 개수
	//가로세로 다리 연결해서 최소값 구하기
	//초기화
	for (int i = 0; i <= islandnum; i++) {
		for (int j = 0; j <= islandnum; j++) {
			Road[i][j] = INF;
		}
	}
	//초기화
	for (int i = 1; i <= islandnum; i++) {
		used[i] = INF;
	}
	//다리 만들기
	makeRoad();
	//트리 만들기
	ans = tree();
	//만약 트리가 끊겨 있다면 -1
	for (int i = 1; i <= islandnum; i++) {
		if (find(i) != find(1)) return -1;
	}

	return ans;
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
		}
	}
	int ans=solve();
	
	printf("%d", ans);
}