백준6118 - 숨바꼭질

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

6118번: 숨바꼭질

처음에는 플루이드 와샬 알고리즘으로 접근하였다가 다익스트라 알고리즘으로 접근하였다.

 

플루이드 와샬 알고리즘으로 접근을 하면 안되었다. 이차원 배열을 이용하여야 하는데 20000 * 20000개를 수행하면 4억개고 4억개의 int형이면 1.6GB이다. 그리고 애초에 1번 마을에서 출발하기 때문에 다 대 다의 마을이동정보가 필요한 것이 아니다. 따라서 이 문제는 다익스트라 알고리즘으로 풀어야 한다.

 

다익스트라는 일 대 다의 마을이동정보가 필요할 때 사용한다. 다익스트라 알고리즘은 출발한 마을로부터 도착한 마을에 비용을 계산하여 배열에 담아놓고 도착한 마을을 다시 큐에 넣는다. 큐에 넣은 마을은 front에 위치한 마을에서 다시 다익스트라 알고리즘을 수행한다. 이렇게 되면 제일 처음 출발한 마을에서 마지막 번째 마을까지 이동하는 비용이 나온다.

 

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

int n, m; //n은 마을의 갯수, m은 가능한 경우
int d[20001]; //d는 다익스트라를 수행한 결과를 저장할 변수
int locate; //가장 먼 거리 중 제일 작은 번호
int big = -1; //가장 먼 거리
int cnt = 0; //locate와 거리가 같은 마을의 갯수
vector<int> v[20001]; //v[x][i] = y에 의미는 x에서 출발하여 k개에 도달할 수 있는 마을이 있다고 가정했을 때 그 중 i번째 마을은 y라는 의미

//다익스트라, 큐를 이용하여 구현
void djikstra(int start) {
	queue<int> q; //다익스트라 수행 후 도착한 위치를 큐로 담는다.
	q.push(start); //처음 시작할 마을을 큐에 넣는다.
	while (!q.empty()) { //모든 마을을 돌 때 까지 수행
		int x = q.front(); //가장 큐에 앞서 저장된 마을을 넣는다.
		q.pop(); //현재 넣은 마을을 팝한다.
		for (int i = 0; i < v[x].size(); i++) { //x번째 마을에서 도달할 수 있는 마을을 모두 탐색
			if (!d[v[x][i]]) { //도달 가능한 마을이 다익스트라를 수행한 결과가 존재하지 않는 경우
				d[v[x][i]] = d[x] + 1; //도달 가능한 마을을 현재 출발한 위치에 마을에서 + 1을 하여 비용을 갱신
				q.push(v[x][i]); //도달 가능한 마을을 다시 큐에 넣는다.
			}
		}
	}
}

int main() {
	//마을의 갯수와 가능한 경우의 수를 입력
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		//왕복이 가능하므로 v[a], v[b] 모두 갱신한다.
		v[a].push_back(b); 
		v[b].push_back(a);
	}

	djikstra(1); //첫번째 마을에서 다익스트라 수행

	//첫번째 마을부터 순회할 필요가 없으니까 두번째 마을부터 순회
	for (int i = 2; i <= n; i++) {
		//최대 거리를 찾으면 최대값과 마을을 갱신
		if (d[i] > big) {
			big = d[i];
			locate = i;
		}
	}

	//locate와 비용이 같은 곳을 찾는다.
	for (int i = 2; i <= n; i++) {
		if (d[i] == big) {
			cnt++;
		}
	}

	cout << locate << ' ' << big << ' ' << cnt;
}