[ 백준/C++] 17472 다리만들기2 (삼성A형 기출문제,BFS,DFS 이용하기)

 

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

파란것은 섬이고 하얀것은 바다

그리고 회색의 다리로 섬들을 최소 길이로 이으라는 문제이다. 

 

문제 자체는 이해하기 어렵지 않다. 

다리는 직선이어야 하고 길이는 2이상이어야 한다. 

그리고 다리는 섬과 섬 사이를 이어야한다. 즉, 다리를 잇는 도중에 다리를 짓는 방향과 다른방향으로 섬이 있다고 해서 섬이 이어졌다고 판단하면 안된다. 

 

그런데 이 문제를 푸는 방법은 좀 생각을 잘 해야 한다. 

코드를 보면 좀 복잡 해 보이겠지만 함수의 이름을 최대한 직관적으로 쉽게 지정해 놓았으니 찬찬히 보면서 이해해 보면 좋을 것 같다. 

 

일단 풀이의 알고리즘 순서는 다음과 같다. 

 

1.dfs()를 이용하여 일단 섬의 개수를 구한다. 

• dfs를 이용하여 동서남북 4방향 다 체크하면서 더 이상 갈 곳이 없으면 빠져나와서 섬 개수를 카운트 한다. 

2. findBridge()를 이용하여 각 섬들간의 최소 다리 길이를 구한다. 

• 1번 섬과 2번 섬을 잇는 다리의 최소 길이는 a
• 2번 섬과 3번 섬을 잇는 다리의 최소 길이는 b
•  n번 섬과 n+1번 섬을 잇는 다리의 최소 길이는 x.. 이런식으로 구한다. 

3. 구한 최소 길이의 다리들을 모두 select_bridge라는 벡터에 넣어두고 조합을 계산한다. ( comb(C,inx,cnt) )

• 예) select_bridge의 길이가 m 이라고 하였을 때,  개의 다리중에서 1,2,5,m-1 번 다리만 사용 하였을 경우, 모든 섬들을 다 잇는지 확인한다. ( CheckConnection() ) 

4. CheckConnection()에서 모든 섬들을 다 잇는 경우에 다리의 길이가 최소 길이인지 확인한다. (bridge_total_len)

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>

int Y, X;
int map[15][15];
int mapnum[15][15];
bool visit[15][15];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int island_num = 0;
struct info { int sn, en, len; };
std::vector<info> bridge;
std::vector<bool> select_bridge;
int ans = 987654321;
int bridge_total_len = 0;

bool connection[10][10];
bool connection_visit[10];

void dfs(int y, int x, int n) { //cnt islands
	visit[y][x] = true;
	mapnum[y][x] = n;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= Y || nx >= X) continue;
		if (map[ny][nx] == 0 || visit[ny][nx]) continue;
		dfs(ny, nx, n);
	}
}
int  findbridge(int sn, int en, int y, int x, int minlen_bridge) {
	int len = 0;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		len = 0;
		while (true) {
			if (ny < 0 || nx < 0 || ny >= Y || nx >= X) break;

			if (mapnum[ny][nx] != en && map[ny][nx] == 1) break;///이게 중요! 
			if (map[ny][nx] == 0) {
				len++;
				ny += dy[i];
				nx += dx[i];
				continue;
			}
			else if (mapnum[ny][nx] == en && len >= 2) {
				//printf("len : %d \n", len);
				minlen_bridge = len < minlen_bridge ? len : minlen_bridge;
				break;
			}
			else// 
				break;
		}
	}
	return minlen_bridge;
}
void checkConnection() {
	memset(connection, 0, sizeof(connection));
	memset(connection_visit, 0, sizeof(connection_visit));

	for (int i = 0; i < bridge.size(); i++) {
		if (select_bridge[i]) {
			connection[bridge[i].sn][bridge[i].en] = true;
			connection[bridge[i].en][bridge[i].sn] = true;
		}
	}
	std::queue<int> Q;
	Q.push(1);
	connection_visit[1] = true;

	int island_cnt = 1;
	bool Flag = false;
	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();

		if (island_cnt == island_num) {
			Flag = true;
			break;
		}

		for (int i = 1; i <= island_num; i++) {
			if (cur == i) continue;
			if (connection[cur][i] && !connection_visit[i]) {
				connection_visit[i] = true;
				Q.push(i);
				island_cnt++;
			}
		}
	}

	if (Flag) {
		ans = ans > bridge_total_len ? bridge_total_len : ans;
	}
}
void comb(int C, int inx, int cnt) { // combination 하는법
	if (cnt == C) {
		bridge_total_len = 0;
		for (int i = 0; i < bridge.size(); i++) {
			if (select_bridge[i]) bridge_total_len += bridge[i].len;
		}

		checkConnection();
		return;
	}
	for (int i = inx; i < bridge.size(); i++) {
		if (select_bridge[i]) continue;
		select_bridge[i] = true;
		comb(C, i + 1, cnt + 1);
		select_bridge[i] = false;
	}
}
int main() {
	scanf("%d %d", &Y, &X);
	for (int y = 0; y < Y; y++) for (int x = 0; x < X; x++) scanf("%d", &map[y][x]);
	// calculate island num
	for (int y = 0; y < Y; y++) {
		for (int x = 0; x < X; x++) {
			if (map[y][x] == 0 || visit[y][x]) continue;
			island_num++;
			dfs(y, x, island_num);
		}
	}
	// find bridge 

	for (int sn = 1; sn <= island_num; sn++) {
		for (int en = sn + 1; en <= island_num; en++) {
			if (sn >= en) continue;
			int minlen_bridge = 999999;
			int minlen_bridge_cand = 999999;
			for (int y = 0; y < Y; y++) {
				for (int x = 0; x < X; x++) {
					if (mapnum[y][x] != sn) continue;
					minlen_bridge_cand = findbridge(sn, en, y, x, 99999999);
					//printf("%d \n", minlen_bridge_cand);
					minlen_bridge = minlen_bridge > minlen_bridge_cand ? minlen_bridge_cand : minlen_bridge;
				}
			}
			if (minlen_bridge != 999999) {
				bridge.push_back({ sn,en,minlen_bridge });
				select_bridge.push_back(false);
			}

		}
	}
    
	for (int C = 1; C <= bridge.size(); C++) {
		for (int i = 0; i < select_bridge.size(); i++) select_bridge[i] = false;
		comb(C, 0, 0);
	}
	if (ans == 987654321) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

 

삼성 코테를 준비하면서 느낀건데 정신을 바짝 차려야 한다.

시뮬레이션이지만 적어도 이런 조합,순열,bfs,dfs를 열심히 돌려서 풀 수 있는 문제라면 희망의 끈을 놓지않고 실수하지 않는 연습을 해야 한다. 

 

나의 경우에는 함수와 변수명의 길이가 길더라도 풀어서 쓰는 것이 그 방법이었다.

왜냐면 코딩을 하다보면 내가 무엇을 하고있는 지 까먹기 때문.. 

이 함수의 input과 output을 정확히 기억하도록 하자. 

 

그리고 문제를 풀다보면 내가 실수하는 유형이 좀 정해져 있다. 

나의 경우에는 일단 오타였고 또 map의 크기, 조건등을 종종 꼼꼼하게 읽지 않아서 틀리는 경우였다.