백준 17472번 다리만들기2 (C++) 🚩

런타임에러 

요즘 왜 자꾸 런타임에러가 뜨지

 

#include<vector>
#include <iostream>
#include<tuple>
#include<queue>
#include<map>

using namespace std;

typedef tuple<int,int,int> tp; 

priority_queue<tp,vector<tp>,greater<tp>>pq;

vector<vector<int>>arr;
vector<vector<bool>>visited;
map<tp,tuple<int,int,int,int>>info;

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

int n,m;

vector<int>parent; 

int find(int node){
    if(parent[node]<0)return node;
    return parent[node]=find(parent[node]);
}

bool unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return false;
    
    if(parent[xp]<parent[yp]){
        parent[xp]+=parent[yp];
        parent[yp]=xp;
    }
    else{
        parent[yp]=parent[xp];
        parent[xp]=yp; 
    }
    return true;
}

void dfs(int i,int j,int num){
    
    visited[i][j]=1; 
    arr[i][j]=num; 
    
    for(int k=0;k<4;k++){
        int nr=i+dr[k];
        int nc=j+dc[k]; 
        
        if(nr<0 || nr>=n || nc<0 || nc>=m)continue;
        if(!visited[nr][nc] && arr[nr][nc]==1){
            dfs(nr,nc,num);
        }
    }
    
}

int main()
{

    cin>>n>>m; 
    parent.assign(n+1,-1);
    arr.assign(n,vector<int>(m,0));
    visited.assign(n,vector<bool>(m,false));
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    
    //섬을 지정하기 
    int num=1; 
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visited[i][j] && arr[i][j]==1){
                dfs(i,j,num);
                num++;
            }
        }
    }
    
    //만들수 있는 다리목록 - (거리,a,b) / 시작점 끝점 
    // i,j에서 시작하는 가로,세로다리
    //양끝에 섬,길이 2이상 
    vector<tp>dist;
    
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            
            if(arr[i][j]!=0)continue; 
            int a=arr[i][j-1];
            int cnt=0; 
            int b; 
            int l;
            bool flag=false;       
            //가로
            if(j>0 && j<m-1){
    
                for(int k=j;k<m;k++){
                   if(arr[i][k]==0)cnt++;
                   else{
                     if(a!=0 && arr[i][k]!=a && cnt>1){
                        b=arr[i][k]; 
                        flag=true; 
                        l=k-1;
                    
                     }
                     break;
                   }
                }
                if(flag && cnt>=2){
                //거리, 두 섬 번호 , 시작점, 끝점 
                   pq.push({cnt,a,b});
                   info[{cnt,a,b}]={i,j,l,0};
                  
                }
            }
            
            if(i>0 && i<n-1){
                  
               //세로 
               a=arr[i-1][j];
               cnt=0; 
               flag=false; 
               for(int k=i;k<n;k++){
                   if(arr[k][j]==0)cnt++;
                   else{
                       if(a!=0 && arr[k][j]!=a && cnt>1){
                            
                          b=arr[k][j]; 
                          flag=true; 
                          l=k-1;
                     
                       }
                       break;
                    }
               }
            
               if(flag && cnt>=2){
                //거리, 두 섬 번호 , 시작점, 끝점 
                pq.push({cnt,a,b});
                info[{cnt,a,b}]={i,j,l,1};
               }
            }
         
        }
    }
   
    //모든 섬 연결하는 mst, 없으면 x 
    int c=0;
    int answer=0;
    while(c<(num-1)){
        
        if(pq.empty()){
            break;
        }
        int w=get<0>(pq.top());
        int a=get<1>(pq.top());
        int b=get<2>(pq.top());

        
        pq.pop();
        
        if(unions(a,b)){
            c++;
            int f=get<0>(info[{w,a,b}]);
            int e=get<1>(info[{w,a,b}]);
            int g=get<2>(info[{w,a,b}]);
            int d=get<3>(info[{w,a,b}]);
            if(d==0){ //가로 
                answer+=(g-e+1);
            }
            else{
                answer+=(g-f+1);
            }
        }
     
    }
   
    if(c==(num-2))cout<<answer;
    else cout<<-1;
    return 0;
}

 

런타임에러가 나는 이유를 찾았다!! 

섬의겟수인 num만큼 parent를 할당해야했는데 지도인 n으로 습관적으로 한것이었다..

 

#include<vector>
#include <iostream>
#include<tuple>
#include<queue>
#include<map>

using namespace std;

typedef tuple<int, int, int> tp;

priority_queue<tp, vector<tp>, greater<tp>>pq;

vector<vector<int>>arr;
vector<vector<bool>>visited;
map<tp, tuple<int, int, int, int>>info;

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

int n, m;

vector<int>parent;

int find(int node) {
    if (parent[node] < 0)return node;
    return parent[node] = find(parent[node]);
}

bool unions(int x, int y) {

    int xp = find(x);
    int yp = find(y);

    if (xp == yp)return false;

    if (parent[xp] < parent[yp]) {
        parent[xp] += parent[yp];
        parent[yp] = xp;
    }
    else {
        parent[yp] = parent[xp];
        parent[xp] = yp;
    }
    return true;
}

void dfs(int i, int j, int num) {

    visited[i][j] = 1;
    arr[i][j] = num;

    for (int k = 0; k < 4; k++) {
        int nr = i + dr[k];
        int nc = j + dc[k];

        if (nr < 0 || nr >= n || nc < 0 || nc >= m)continue;
        if (!visited[nr][nc] && arr[nr][nc] == 1) {
            dfs(nr, nc, num);
        }
    }

}

int main()
{

    cin >> n >> m;

   
    arr.assign(n, vector<int>(m, 0));
    visited.assign(n, vector<bool>(m, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    //섬을 지정하기 
    int num = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && arr[i][j] == 1) {
                dfs(i, j, num);
                num++;
            }
        }
    }
    parent.assign(num+1, -1); //이거였음
    //만들수 있는 다리목록 - (거리,a,b) / 시작점 끝점 
    // i,j에서 시작하는 가로,세로다리
    //양끝에 섬,길이 2이상 
   
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            if (arr[i][j] != 0)continue;
            int a;
            int cnt = 0;
            int b;
            int l;
            bool flag = false;
            //가로
            if (j > 0 && j < m - 1) {
                a = arr[i][j - 1];
                for (int k = j; k < m; k++) {
                    if (a == 0)break; 
                    if (arr[i][k] == 0)cnt++;
                    else {
                        if (arr[i][k] != a && cnt > 1) {
                            b = arr[i][k];
                            flag = true;
                            l = k - 1;

                        }
                        break;
                    }
                }
                if (flag && cnt >= 2) {
                    //거리, 두 섬 번호 , 시작점, 끝점 
                    pq.push({ cnt,a,b });
                    info[{cnt, a, b}] = { i,j,l,0 };

                }
            }

            if (i > 0 && i < n - 1) {

                //세로 
                a = arr[i - 1][j];
                cnt = 0;
                flag = false;
                for (int k = i; k < n; k++) {
                    if (a == 0)break;
                    if (arr[k][j] == 0)cnt++;
                    else {
                        if (arr[k][j] != a && cnt > 1) {
                            b = arr[k][j];
                            flag = true;
                            l = k - 1;

                        }
                        break;
                    }
                }

                if (flag && cnt >= 2) {
                    //거리, 두 섬 번호 , 시작점, 끝점 
                    pq.push({ cnt,a,b });
                    info[{cnt, a, b}] = { i,j,l,1 };
                }
            }

        }
    }

    //모든 섬 연결하는 mst, 없으면 x 
    int c = 0;
    int answer = 0;
    while ( c < (num - 1)) {

        if (pq.empty())break;
        int w = get<0>(pq.top());
        int a = get<1>(pq.top());
        int b = get<2>(pq.top());

        pq.pop();

        if (unions(a, b)) {
            c++;
            int f = get<0>(info[{w, a, b}]);
            int e = get<1>(info[{w, a, b}]);
            int g = get<2>(info[{w, a, b}]);
            int d = get<3>(info[{w, a, b}]);
            if (d == 0) { //가로 
                answer += (g - e + 1);
                for (int aa = e; aa <= g; aa++) {
                    arr[f][aa] = 9;
                }
            }
            else {
                answer += (g - f + 1);
                for (int aa = f; aa <= g; aa ++) {
                    arr[aa][e] = 9;
                }
            }
        }

    }
    

    if (c < (num - 2))cout << -1;
    else cout << answer;
   
    return 0;
}