[백준]다리만들기2

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

17472번: 다리 만들기 2

 

상당히 구현할 량도 많고 그래프도 복잡한 문제 ..

복구 한 것에서 틀린 부분은 일직선 거리가 아니라 옆으로도 갈 수 있는 것이다..또한 완전탐색 실수

 

그래서 한칸 갈때마다 뒷방향을 제외한 나머지 3방향에 대한 길의 여부를 통해 거리를 측정해주었다.

그리고 원래는 최소값을 찾아서 int형으로 return을 해주었는데 그렇게 되면 최소의 거리를 찾고 그 다음의 다른섬으로 가는 길목이 막히게 되어서 그냥 void형 함수로 끝까지 탐색해준 후, 최소값을 갱신해주었다.

또한, dfs를 사용할 때 완전탐색으로 해주었어야 했는데 true를 남겨주는 방식으로해서 지나온길을 다시 지나가지 않는 문제가 생겼었다. 그래서 true->false로 설정해주어 모든길에 대해 탐색하고 길이가 섬의 개수일 때 최소값을 갱신해주었다. ( 상황에 따라서 잘 구분해서 사용해야 할 것 같다... 헷갈리기 쉬움)

포인트1. 단지번호 붙이기 (dfs)로 각 섬의 번호를 인덱싱.

포인트2. 그 후, 섬과 섬사이의 거리를 구해준다. 이때, 일직선으로만 갈 수 있는것이 아닌것이 중요함.

포인트3. 각 섬사이의 가중치 그래프를 구한 후, mst 혹은 dfs완전탐색(각 정점마다) 탐색하며 가중치의 최소값을 찾는다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct INFO {
    int r, c;
};
 
int N, cnt = 1;
int R, C;
int map[10][10];
bool isV[10][10];
int Dis[6][6];
bool isV2[6];
int dr[] = { -1,0,1,0 }, dc[] = { 0,1,0,-1 };
queue<INFO> q;
int ans = 1e9;
 
void dfs(int r, int c, int val) { //인접한 섬들 묶기
    isV[r][c] = true;
    map[r][c] = val;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (!isV[nr][nc] && map[nr][nc]) {
            dfs(nr, nc, val);
        }
    }
}
 
void div() { //섬 인덱싱
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!isV[i][j] && map[i][j]) {
                dfs(i, j, cnt);
                cnt++;
            }
        }
    }
}
 
void move(int r, int c, int d, int start) { //다른 섬찾을때까지 이동
    int nr = r, nc = c;
    int dis = 0;
    while (1) {
        dis++;
        nr = nr + dr[d], nc = nc + dc[d];
        if (map[nr][nc] == start) return; //내부 거르기
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) return;//범위 체크
 
        for (int i = 0; i < 4; i++) {
            if ((d+2)%4 == i) continue; //반대방향거르기
            int nnr = nr + dr[i], nnc = nc + dc[i];
            if (nnr < 0 || nnc < 0 || nnr >= R || nnc >= C)continue;
            if (map[nnr][nnc] != start && map[nnr][nnc]) {
                if (Dis[start][map[nnr][nnc]] >= dis) Dis[start][map[nnr][nnc]] = dis, Dis[map[nnr][nnc]][start] = dis;
            }
        }
    }
}
 
void bfs(int start) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) { //시작점 입력
            if (map[i][j] == start) q.push({ i,j });
        }
    }
    while (!q.empty()) {
        int r = q.front().r, c = q.front().c; q.pop();
        for (int i = 0; i < 4; i++) move(r, c, i, start); //섬들과의 거리
    }
}
 
void dfs2(int s, int len, int SUM) {
    if (len == cnt - 1) { //모든 섬을 탐색했을때 최소값 갱신
        if (ans >= SUM) ans = SUM;
        return;
    }
    
    for (int i = 1; i < cnt; i++) {
        if (!isV2[i] && Dis[s][i] != 0) { //글로벌로할지 파라미터로할지 구분잘해야함.
            isV2[i] = true;
            dfs2(i, len + 1, SUM + Dis[s][i]);
            isV2[i] = false;
        }
    }
}
 
void solve() {
    div(); //섬 인덱싱
    for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) Dis[i][j] = 20;
    for (int i = 1; i < cnt; i++) bfs(i); //각 섬에서 부터 출발해서 거리가중치 구하기
 
    for (int i = 1; i < cnt; i++) {
        for (int j = 1; j < cnt; j++) {
            if (Dis[i][j] == 20) Dis[i][j] = 0;
        }
    } //없는 길 0 으로 초기화.
 
    for (int i = 1; i < cnt; i++) { //각 정점에서 출발하는 가중치 완전탐색
        if (!isV2[i]) {
            isV2[i] = true;
            dfs2(i, 1, 0);
            isV2[i] = false;
        }
    }
    printf("%d\n", ans == 1e9 ? -1 : ans); //길없으면 -1
}
 
int main()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> map[i][j];
    solve();
    return 0;
}

 

 

계속 조건이 바뀐다 .... 이번엔 걍 직선다리 && 길이가 1인 다리는 없는 조건.

마지막 답은 Prim알고리즘을 통해 최소 cost를 구해주었다. 

Prim 알고리즘 참고 : https://victorydntmd.tistory.com/102

[알고리즘] MST(3) - 프림 알고리즘 ( Prim's Algorithm )

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct INFO {
    int r, c;
};
 
int N, cnt = 1, R, C, ans = 1e9;
int map[10][10], Dis[7][7];
bool isV[10][10];
int dr[] = { -1,0,1,0 }, dc[] = { 0,1,0,-1 };
queue<INFO> q;
 
void dfs(int r, int c, int val) { //인접한 섬들 묶기
    isV[r][c] = true;
    map[r][c] = val;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (!isV[nr][nc] && map[nr][nc]) {
            dfs(nr, nc, val);
        }
    }
}
 
void div() { //섬 인덱싱
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!isV[i][j] && map[i][j]) {
                dfs(i, j, cnt);
                cnt++;
            }
        }
    }
}
 
void move(int r, int c, int d, int start) { //다른 섬찾을때까지 이동
    int nr = r, nc = c;
    int dis = 0;
    while (1) {
        dis++;
        nr = nr + dr[d], nc = nc + dc[d];
        if (map[nr][nc] == start) return; //내부 거르기
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) return; //범위 체크
        if (map[nr][nc] != start && map[nr][nc] && dis == 2) return;
        if (map[nr][nc] != start && map[nr][nc] && dis != 2) {
            if (Dis[start][map[nr][nc]] >= dis-1) {Dis[start][map[nr][nc]] = dis-1, Dis[map[nr][nc]][start] = dis-1; return;}
 return; //예외로 저격당해서 처리. 이미 최소가 구해져있으면 다른곳에선 다른 지점을 만나도 return이 안됨
        }
    }
}
 
void bfs(int start) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) { //시작점 입력
            if (map[i][j] == start) q.push({ i,j });
        }
    }
    while (!q.empty()) {
        int r = q.front().r, c = q.front().c; q.pop();
        for (int i = 0; i < 4; i++) move(r, c, i, start); //섬들과의 거리
    }
}
 
int findMin(int minWeight[], bool isV[]) {
    int min = 1e9, minidx = -1;
    for (int i = 1; i < cnt; i++) {
        if (!isV[i] && minWeight[i] < min) min = minWeight[i], minidx = i;
   } //방문 안한 정점들 중에서 가장 최소 값을 갖는 정점의 인덱스 반환
    return minidx;
}
 
void Prim() {
    int minWeight[7]; //각 정점으로 가는 최소 cost배열
    bool isV[7]; //방문여부
    for (int i = 1; i < cnt; i++) minWeight[i] = 1e9, isV[i] = false; //무한대값으로 초기화
    
    minWeight[1] = 0; //1부터 시작
    for (int count = 0; count < cnt - 1; count++) { //정점-1번 실행.
        int u = findMin(minWeight, isV); //방문 안한 값들중 최소 값 인덱스 찾기.
        if (u == -1) continue; //갈수 있는 곳 없음.
        isV[u] = true; // 가장 작은 정점에서부터 방문시작.
 
        for (int v = 1; v < cnt; v++) { //모든 정점들을 탐색
            if (Dis[u][v] && !isV[v] && Dis[u][v] < minWeight[v]) {
                minWeight[v] = Dis[u][v];
            }
        }
    }
    bool flag = false;
    for (int i = 1; i < cnt; i++) { //방문 안한것 있는지 체크
        if (!isV[i]) { flag = true; break; }
    }
    if (!flag) {//전부다 방문했으면 답 갱신.
        ans = 0;
        for (int i = 1; i < cnt; i++) ans += minWeight[i];
    }
}
 
 
void solve() {
    div(); //섬 인덱싱
    for (int i = 1; i <= 6; i++) for (int j = 1; j <= 6; j++) Dis[i][j] = 20;
    for (int i = 1; i < cnt; i++) bfs(i); //각 섬에서 부터 출발해서 거리가중치 구하기
 
    for (int i = 1; i < cnt; i++) {
        for (int j = 1; j < cnt; j++) {
            if (Dis[i][j] == 20) Dis[i][j] = 0;
        }
    } //없는 길 0 으로 초기화.
 
    Prim();
    printf("%d\n", ans == 1e9 ? -1 : ans); //길없으면 -1
}
 
int main()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> map[i][j];
    solve();
    return 0;
}