[BaekJoon/백준] 14218번: 그래프 탐색 2(C/C++)

백준 14218번: 그래프 탐색 2

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

14218번: 그래프 탐색 2

---

문제 설명

남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.

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

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

---

입력과 출력

입력: 첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000)

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

수도는 1번도시이다.

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

---

접근 방법

이번 문제는 도시(정점) N과 도로(간선) M을 입력받은 후, M개의 줄에 걸쳐서 그래프를 만든다. 이후 도로 정비 계획(추가할 간선 수) Q를 입력하고, Q개의 줄에 걸쳐 그래프에 간선을 추가해서 각 도시~수도(1번)까지 최소 경로를 출력하면 된다.

가중치가 없는 문제이므로, BFS를 사용해서 쉽게 해결할 수 있다. 그래프 문제이므로 구조체를 선언하고, 연결된 정점을 저장하는 queue와 함께 사용할 front, rear 변수 그리고 방문했는지 하지 않았는지 확인하고 1에 도착하는 최단 경로를 저장하는 visited 배열도 추가로  선언해서 진행했다.

---

코드

#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

typedef struct Graph {
	int n;
	int adj_mat[MAX][MAX];
} Graph;

int queue[MAX], front, rear;
int visited[MAX];

void init(int N) {
	front = 0;
	rear = 0;
	for (int i = 1; i <= N; i++)
		visited[i] = 0;
}

void insert_edge(Graph *g, int i, int j) {
	g->adj_mat[i][j] = g->adj_mat[j][i] = 1;
}

void BFS(Graph *g) {
	int pop;
	init(g->n);
	queue[rear++] = 1;
	visited[1] = 1;
	while (front != rear) {
		pop = queue[front++];
		for (int i = 1; i <= g->n; i++)
			if (!visited[i] && g->adj_mat[pop][i] == 1 && g->adj_mat[i][pop] == 1) {
				queue[rear++] = i;
				visited[i] = visited[pop] + 1;
			}
	}
}

int main(int argc, char *argv[]) {
	Graph *g;
	int N, M, Q;
	int i, j;
	int count;

	g = (Graph *)malloc(sizeof(Graph));

	scanf("%d %d", &N, &M);
	g->n = N;
	for (count = 0; count < M; count++) {
		scanf("%d %d", &i, &j);
		insert_edge(g, i, j);
	}

	scanf("%d", &Q);
	for (count = 0; count < Q; count++) {
		scanf("%d %d", &i, &j);
		insert_edge(g, i, j);

		BFS(g);
		
		for (int count2 = 1; count2 <= N; count2++)
			printf("%d ", visited[count2] - 1);
		printf("\n");
	}

	return 0;
}

---

결과

백준 제출 결과