[ 백준 17472 ] 다리 만들기2 (C++)

[문제보기]

 

[해결과정]

 

 1. 입력 받기 (n, m, arr[][])

 2. 섬 번호 메기기

   -> gNum 변수 선언 (섬 번호 Count)

   -> arr 배열을 돌면서, 1이면서 방문하지 않은 곳이라면 q(큐)에 좌표 넣기

   -> bq(또 다른 큐)는 추후 해당 좌표가 다른 섬이랑 연결 될 수 있는지 확인 하기 위한 것

   -> 해당 좌표에 map배열에 gNum 입력과 방문체크 후 BFS() 실행

       -> 해당 좌표에서 상,하,좌,우에 1이 있다면 방문체크 후, q(큐), bq(큐)에 넣기.

       -> 다음 좌표의 map에는 gNum(섬 번호) 입력.

 

 ★★★ 여기서 섬들의 좌표가 잘 찍혔는지 map을 print 해서 디버깅 한번 해보기!!!

 

 3. 2번 과정에서 bq(큐)에 넣은 값들을 하나씩 꺼내보며, 다른 섬으로 갈 수 있는지 확인

   -> 상,하,좌,우 해당 좌표와 같은 gNum이거나, 맵 크기를 벗어나면 다음 방향.

   -> 섬이 나타날때까지 전진하며 cnt를 증가시킴.

   -> 섬 발견 시 vector에 (출발 섬, 도착 섬, 섬 사이의 길이) push.

   -> 위와 같은 방식으로 bq(큐)를 모두 탐색.

 

 ★★★ 여기서 vector에 (출발 섬, 도착 섬, 길이)가 잘 저장 되어 있는지 디버깅 한번 해보기!!!

 

 4. MST 사용

   -> parent 배열을 생성하고, 원소를 자기 자신의 값으로 설정. 1=1, 2=2, 3=3 ...

   -> 섬 간선 정보가 저장된 vector를 길이 순서대로 정렬

   -> Union Find 실행

       -> 실행하며 섬 정보를 담는 c(vector)에 출발섬, 도착섬을 저장

       -> 길이를 ans 에 합산 시키며 진행

 

 5. 4번에서 처음 수행된 섬정보를 가지고 BFS 수행

   -> 가장 처음 저장된 섬을 통해 나머지 모든 섬을 갈 수 있는지 BFS로 확인

 

 6. 모든 섬을 방문 했는 지 확인하고 결과 도출

   -> 모든 섬을 방문 했다면 ans 출력

   -> 하나라도 방문하지 않았거나, ans==0 이라면 -1 출력

 

[소스코드]

/*
    BOJ 17472 - 다리 만들기2
    Created by haejun on 2020/02/22
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;
const int MAX = 12;
 
int n, m;
int arr[MAX][MAX];
int map[MAX][MAX];
bool check[MAX][MAX];
 
// 구조체, 구조체 큐 생성
struct coor {
    int y;
    int x;
    int num;
};
queue <coor> q;
 
// 다리 조사할 때 다시 조사할 큐 생성
queue <coor> bq;
 
// 그룹 번호 지정
int gNum = 1;
 
// 외곽 벗어나는지 inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
// 다리 연결할 vector 생성
// a -> b 까지 길이 c;
struct bridge {
    int a;
    int b;
    int c;
};
vector <bridge> v;
 
bool cmp(const bridge & a, const bridge & b) {
    if (a.c < b.c) return true;
    else return false;
}
 
 
// MST를 위한 변수
int p[102];
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int num = q.front().num;
        q.pop();
        
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] == 1) {
                check[ny][nx] = 1;
                map[ny][nx] = num;
                q.push({ ny,nx,num });
                bq.push({ ny,nx,num });
            }
        }
    }
}
 
int find(int x) {
    if (p[x] == x) return x;
    else return p[x] = find(p[x]);
}
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    p[a] = b;
}
bool sp(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) return false;
    else return true;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    // 1. input
    memset(check, 0, sizeof(check));
    cin >> n >> m;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j];
 
    // 2. 섬 번호 메기기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1 && check[i][j] == 0) {
                check[i][j] = 1;
                map[i][j] = gNum;
                q.push({ i,j,gNum });
                bq.push({ i,j,gNum });
                bfs();
                gNum++;
            }
        }
    }
 
    // 3. 섬에서 다른 섬 갈 수 있는지 확인하고,
    // vector에 (섬1 , 섬2 , 거리) 로 넣기
    memset(check, 0, sizeof(check));
    while (!bq.empty()) {
        int y = bq.front().y;
        int x = bq.front().x;
        int num = bq.front().num;
        bq.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            int s = 1;
            int cnt = 1;
            while (true) {
                ny = y + dy[i] * s;
                nx = x + dx[i] * s;
                if (!inside(ny, nx)) break;
                if (map[ny][nx] == num) break;
                if (map[ny][nx] != 0 && map[ny][nx] != num) {
                    if (cnt - 1 >= 2) v.push_back({ num, map[ny][nx], cnt - 1 });
                    break;
                }
                s++;
                cnt++;
            }
        }
    }
 
 
    // 4. Union Find, MST 사용
    for (int i = 1; i < 102; i++) p[i] = i;
 
    sort(v.begin(), v.end(), cmp);
 
    
    // 5. BFS로 한 정점에서 모든 정점으로 갈 수 있는지,
    int ans = 0;
    vector <int> c[7];
    bool check2[102] = { 0, };
    queue <int> lq;
    int m = 0;
    for (int i = 0; i < v.size(); i++) {
        if (sp(v[i].a, v[i].b) == false) {
            Union(v[i].a, v[i].b);
            ans += v[i].c;
            c[v[i].a].push_back(v[i].b);
            c[v[i].b].push_back(v[i].a);
            if (m == 0) m = v[i].a;
        }
    }
 
    lq.push(m);
    while (!lq.empty()) {
        int num = lq.front();
        lq.pop();
        check2[num] = true;
        for (int i = 0; i < c[num].size(); i++) {
            if (check2[c[num][i]] == false) {
                check2[c[num][i]] = true;
                lq.push(c[num][i]);
            }
        }
    }
 
    
 
    bool flag = false;
    for (int i = 1; i < gNum; i++) {
        //cout << check2[i] << " ";
        if (check2[i] == false) flag = true;
    }
 
    if (flag == false) cout << ans << "\n";
    else cout << -1 << "\n";
 
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 이 문제는 생에 두 번째 A형 시험을 보며 나왔던 문제이다. MST를 이 때 알게 되었다... 이때 1번 문제도 아마 Union Find를 써야하는 문제였던 것으로 안다....

 

 일단 굉장히 복잡하다. 왜 골드 4밖에 안되는지 이해하기 힘들다; 본론으로 들어가서 해결 과정 중 많은 실수를 했다.. 그런데 처음, 중간.. 심지어 결과까지 잘 나왔는데 계속 틀렸다... 결과를 도출하는 부분이 잘못되었었다..

 

 1. 처음에는 Union Find를 수행해서 부모와 자식 값 즉 1 1 1 4 혹은 4 4 4 3 같은 형태로 두 개의 수만 존재하면, 모든 섬이 연결되었을 것이라 착각했다... 이럴 경우, 3가지 방향이상으로 흩어질 경우 문제가 생긴다...

 

 2. 그래서 더 생각 한 것이, 그냥 Union Find 할 때 들어가면서 해당 섬은 방문했다고 체크 하는 것이였다.. 이럴 경우, 연결이 되지 않았는데... 단지 간선이 있단 것 만으로 연결 되었다고 될 수 있기에 틀렸다...

 

 그래서 결론적으로는 또 BFS를 써야했던 것이다. 섬중에 아무 섬이나 넣고 돌리면 모든 섬이 방문했는지 안했는지 알 수 있으니까...

 

 사실 시간복잡도가 길어질 것 같아서, 쓰지 않았는데 멍청이!!!!!!!!!!!!!! 섬은 최대 갯수가 단 6개 밖에 되지 않았다 ^^.. 문제를 또 제대로 읽지 않았던 것이다 ㅎㅎ..................................... "문제를 꼼꼼히! 제대로! 읽자!!!!!!!!"

 

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트