BOJ 17142 다리 만들기 2

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

DFS + 크루스칼 문제이다.

섬을 알아내기 위해 DFS로 섬 영역을 탐색했고, 탐색하면서 번호를 붙여 같은 섬이면 같은 번호가 할당하게끔 했다.

 

간선을 알아내기 위해 섬의 격자에서 상하좌우로 탐색을 실시했고, 지도의 끝부분에 가거나 격자의 값이 0이 아닐 때 까지 탐색했다.도착한 격자의 값이 0이 아니면, {거리, {시작 격자, 도착 격자}} 의 구조로 edge에 추가하였다. 

이때, 시작격자와 도착 격자가 같은 경우는 고려하지 않아도 되는데, 이는 크루스칼 알고리즘의 DSU의 merge함수에서 parent가 같은 경우 간선 비용이 추가되지 않기 때문이다.

아래는 내 코드이다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, pair<int, int>>> edge;
vector<pair<int, int>> node;
int parent[7] {0,1,2,3,4,5,6}; //1-based

int n,m;
int map[10][10];
bool visited[10][10];

int answer = 0;


int dr[4]={1,-1,0,0};
int dc[4]={0,0,-1,1};

int find(int a){
    if(parent[a] != a) return parent[a] = find(parent[a]);
    else return a;
}

void merge(int a, int b, int c){
    a = find(a);
    b = find(b);

    if(a == b) return;
    else{
        parent[b] = a;
        answer += c;
    }
}

void dfs(int r, int c, int num){

    if(r >= n || r < 0 || c >= m || c < 0) return;
    if(!map[r][c]) return;
    if(visited[r][c]) return;
    map[r][c] = num;
    visited[r][c] = true;
    for(int i=0;i<4;i++){
        int nextr = r + dr[i];
        int nextc = c + dc[i];
        dfs(nextr, nextc, num);
    }
}

void make_edge(int r, int c, int num){

    visited[r][c] = true;
    for(int i=0;i<4;i++){
        int nextr = r + dr[i];
        int nextc = c + dc[i];
        
        if(nextr >= n || nextr < 0 || nextc >= m || nextc < 0) continue;
        if(visited[nextr][nextc]) continue;
        if(map[nextr][nextc]==num)
            make_edge(nextr, nextc, num);
        else{
            int count = 0;
            while(true){
                nextr += dr[i];
                nextc += dc[i];
                count += 1;

                if(nextr >= n || nextr < 0 || nextc >= m || nextc < 0) break;
                if(map[nextr][nextc]){
                    if(count >= 2){
                        edge.push_back({count, {num, map[nextr][nextc]}});
                        //printf("count : %d, direction : %d, (%d, %d) %d<=>%d\n", count, i, r, c, num, map[nextr][nextc]);
                    }
                    break;
                }
            }
        }
    }
}

bool check(){
    int target = find(1);
    for(int i=2;i<=node.size();i++){
        if(find(i)!=target) return false;
    }
    return true;
}

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);
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(map[i][j] && !visited[i][j]){
                node.push_back({i,j});
                dfs(i,j, node.size());
            }
        }
    }
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            visited[i][j] = false;
    for(int i=0;i<node.size();i++){
        make_edge(node[i].first, node[i].second, i+1);
    }

    sort(edge.begin(), edge.end());

    for(auto e : edge){
        merge(e.second.first, e.second.second, e.first);
    }

    if(check()) printf("%d\n",answer);
    else printf("-1\n");
    
    return 0;
}

 

P.S.나는 visited를 다시 초기화하는 memset 때문에 계속 틀렸었다.

왜 memset을 쓰면 안되는지 아직도 찾지 못했다.

다음과 같은 코드를 돌려봐도 결과는 0으로 초기화 되는데.... 환경 차이인가??

추후 찾아보기로 했다.

#include <cstring>
#include <cstdio>
int main(){
    bool arr[10][10];
    for(int i=0;i<10;i++) for(int j=0;j<10;j++) arr[i][j] = true;
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    memset(arr, false, sizeof arr);
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    return 0;

}

결과

~$ ./test 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0