🧡 Programming/💻 코딩 테스트
[ 백준/C++] 17472 다리만들기2 (삼성A형 기출문제,BFS,DFS 이용하기)
g_____
2023. 2. 12. 22:55
파란것은 섬이고 하얀것은 바다
그리고 회색의 다리로 섬들을 최소 길이로 이으라는 문제이다.
문제 자체는 이해하기 어렵지 않다.
다리는 직선이어야 하고 길이는 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의 크기, 조건등을 종종 꼼꼼하게 읽지 않아서 틀리는 경우였다.