[BOJ/Gold 5] 백준 14217 그래프 탐색(C++)

문제 링크

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

14217번: 그래프 탐색

 

 

문제

남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다. 상황에 따라서는 계획에 포함돼서 만들어진 도로를 제거할 수도 있다.

Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.

남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오.

입력

첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤500,1≤m≤n*(n-1)/2)

다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q줄에는 a i j가 주어지는데, a가 1일때는 두 도시 i,j를 잇는 도로를 만들고, a가 2일때는 i,j를 잇는 도로를 없앤다. (1≤q≤500,1≤a≤2, 1≤i,j≤n)

두 도시 사이에 이미 도로가 있는데 또 도로를 만들거나, 도로가 없는데 없애는 불가능한 경우는 입력으로 들어오지 않는다.

수도는 1번도시이다.

출력

q줄에 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오. 만약 수도를 방문하지 못한다면 -1을 출력하시오.

예제 입력 1

5 6
1 2
1 3
2 4
2 5
3 5
4 5
5
2 1 2
1 1 4
2 2 4
2 2 5
1 1 2

예제 출력 1

0 3 1 3 2
0 2 1 1 2
0 3 1 1 2
0 -1 1 1 2
0 1 1 1 2

알고리즘 분류

• 그래프 탐색

풀이

M개의 도로를 놓았다는 것을 기록하기 위해 500 X 500 크기의 bool 자료형의 이차원 배열을 선언한다. X 도시와 Y 도시를 잇는 도로가 존재한다면 true, 존재하지 않는다면 false이다.

그리고 Q번의 도로 정비 계획을 입력받는다. 각각의 도로 정비 계획에서 A의 값에 따라 I, J 간 도로를 놓거나 철거한 후 BFS를 통해 2 ~ N번 도시에서 수도인 1번 도시까지 가는 데 필요한 최소 방문 도시의 개수를 구하고 공백으로 구분해 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 501
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, Q, X, Y, A, I, J;
bool Bridge[MAX][MAX];
int Answer[MAX];

void init() {
    for (int i = 0; i < MAX; i++) {
        Answer[i] = INF;
    }
}

void make_Bridge(int NowI, int NowJ) {
    Bridge[NowI][NowJ] = true;
    Bridge[NowJ][NowI] = true;
}

void break_Bridge(int NowI, int NowJ) {
    Bridge[NowI][NowJ] = false;
    Bridge[NowJ][NowI] = false;
}

void BFS() {
    queue<pair<int, int> > Queue;
    Answer[1] = 0;
    Queue.push(make_pair(1, 0));

    while (!Queue.empty()) {
        int NowX = Queue.front().first;
        int NowT = Queue.front().second;
        Queue.pop();

        for (int i = 1; i <= N; i++) {
            if (NowX == i) {
                continue;
            }
            if (Bridge[NowX][i] && (Answer[i] > NowT + 1)) {
                Answer[i] = NowT + 1;
                Queue.push(make_pair(i, NowT + 1));
            } 
        }
    };
}

void settings(int NowA, int NowI, int NowJ) {
    if (NowA == 1) {
        make_Bridge(NowI, NowJ);
    }
    else {
        break_Bridge(NowI, NowJ);
    }
    init();
    BFS();
}

void find_Answer() {
    for (int i = 1; i <= N; i++) {
        if (Answer[i] == INF) {
            cout << "-1 ";
        }
        else {
            cout << Answer[i] << " ";
        }
    }
    cout << "\n";
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> X >> Y;
        Bridge[X][Y] = true;
        Bridge[Y][X] = true;
    }
    cin >> Q;
    while (Q--) {
        cin >> A >> I >> J;
        settings(A, I, J); 
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}