백준 2146. 다리 만들기 (C++)

요약

BFS

문제

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

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
struct Node {
    int row, col;
};
queue<Node>q;
vector<Node>v;
int map[101][101] = { 0, };
int visited[101][101] = { 0, };
int checkmap[101][101] = { 0, };
int dr[4] = { 0,0,-1,1 };
int dc[4] = { -1,1,0,0 };
queue<Node>sg;
queue<Node>sgnext;

void init() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if(map[i][j]) v.push_back({ i,j });
        }
    }
}

int setting() {
    int cnt = 1;
    for (int i = 0; i < v.size(); i++) {
        if (visited[v[i].row][v[i].col]) continue;
        q.push({ v[i].row, v[i].col });
        visited[v[i].row][v[i].col] = cnt;
        while (!q.empty()) {
            Node now = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nr = now.row + dr[d];
                int nc = now.col + dc[d];
                if (nr < 1 || nc < 1 || nr > N || nc >N) continue;
                if (map[nr][nc] == 0) continue;
                if (visited[nr][nc]) continue;
                visited[nr][nc] = cnt;
                q.push({ nr,nc });
            }
        }
        cnt++;
    }
    return cnt - 1;
}

int checking(int start) {

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            checkmap[i][j] = visited[i][j];
            if (visited[i][j] == start) {
                int flag = 0;
                for (int d = 0; d < 4; d++) {
                    int nr = i + dr[d];
                    int nc = j + dc[d];
                    if (nr <1 || nc <1 || nr >N || nc >N) continue;
                    if (visited[nr][nc] == 0) flag = 1;
                }
                if(flag == 1) sg.push({ i,j });
            }
        }
    }

    int cnt = 1;
    while (!sg.empty()) {
        while (!sg.empty()) {
            Node now = sg.front();
            sg.pop();

            for (int d = 0; d < 4; d++) {
                int nr = now.row + dr[d];
                int nc = now.col + dc[d];
                if (nr <1 || nc <1 || nr >N || nc >N) continue;
                if (checkmap[nr][nc] < 0) continue;
                if (checkmap[nr][nc] > 0 && checkmap[nr][nc] != start) return cnt - 1;
                checkmap[nr][nc] = (-1) * cnt;
                sgnext.push({ nr,nc });
            }
        }
        while (!sgnext.empty()) {
            sg.push({ sgnext.front() });
            sgnext.pop();
        }
        cnt++;
    }
    return -1;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int groupcnt = setting();
    int ans = 2e9;
    for (int i = 1; i < groupcnt; i++) {
        int nowdist = checking(i);
        if (nowdist < ans && nowdist > 0) ans = nowdist;
        while (!sg.empty())sg.pop();
        while (!sgnext.empty())sgnext.pop();

    }
    cout << ans;

    return 0;
}

오류 발생 풀이

1. 섬과 섬까지 못 가는 경우도 있다는 것을 간과 [Runtime Error : Double Free]
2. checking 함수를 출발지와 도착지를 모두 넣어서 각 섬의 외곽에서 다른 모든 섬까지의 거리를 다 구하는 방법 사용(왜그랬지이건진짜..) [시간 초과]

checking(int start, int end) 해서 다음 좌표의 값이 end일 경우 cnt 를 return하게 코드를 짰었다.
그럼 int nowdist = checking(s,e); 에서 값을 반환받지 못하는데
이렇게 되면 Runtime Error (Double Free) 가 뜬다...
처음보는 런타임에러였고 할당이 해제된 메모리. 포인터를 다시 할당 해제하는 경우 나오고, 인덱스 문제인 경우가 많대서 당연히 벡터나 큐의 문제인 줄 알고 그것만 빤히 쳐다보느라 해결하는데에 시간이 정말 많이 걸렸다 ㅠㅠ ..

나같은 실수를 하는 사람도 없어서 질문게시판에서도 소득도 없고 진지하게 첫 질문 남길까 고민함 ㅋㅋ ㅠ