그래프(Graph)

BFS

Contents

이번 문제에서 그래프는 다음과 같이 구성된다. 

1부터 n까지의 노드로 구성된다. 

각 노드는 이어져있을 수도 있고 그렇지 않을 수도 있다. 

간선의 방향은 없다.

BFS로 방문 할 때 숫자 순으로 방문한다. 예를 들어서 1번 노드에 2번 노드와 3번 노드가 동시에 이어져 있을 경우, 1번 노드에서는 2번 노드를 먼저 방문한다. 

그래프 G와 출발점 s가 주어졌을 때, s에서 출발하는 BFS를 하면서 방문하는 노드를 출력하라.

Input

입력의 첫줄은 n이 들어온다. 그 다음 줄에는 간선의 수 m이 들어온다. 

다음 m 줄에는 간선(x, y)이 들어온다.

마지막 줄에는 출발 노드 s가 들어 온다. 

Output

s에서 출발하여 BFS를 하면서 방문하는 노드를 출력한다. 각 노드는 빈칸으로 구별한다.

Sample Input

5

6

1 3

1 2

1 5

2 3

3 4

4 5

1

 

Sample Output

1 2 3 5 4

=================================================================

DFS

Contents

이번 문제에서 그래프는 다음과 같이 구성된다. 

1부터 n까지의 노드로 구성된다. 

각 노드는 이어져있을 수도 있고 그렇지 않을 수도 있다. 

간선의 방향은 없다.

DFS로 방문 할 때 숫자 순으로 방문한다. 예를 들어서 1번 노드에 2번 노드와 3번 노드가 동시에 이어져 있을 경우, 1번 노드에서는 2번 노드를 먼저 방문한다. 

그래프 G와 출발점 s가 주어졌을 때, s에서 출발하는 DFS를 하면서 방문하는 노드를 출력하라.

Input

입력의 첫줄은 n이 들어온다. 그 다음 줄에는 간선의 수 m이 들어온다. 

다음 m 줄에는 간선(x, y)이 들어온다.

마지막 줄에는 출발 노드 s가 들어 온다. 

Output

s에서 출발하여 dfs를 하면서 방문하는 노드를 출력한다. 각 노드는 빈칸으로 구별한다.

Sample Input

5

6

1 3

1 2

1 5

2 3

3 4

4 5

1

 

Sample Output

1 2 3 4 5

=================================================================

Prim's

Contents

다음은 MST를 구하기 위한 여러 알고리즘 중 하나인 Prim's Algorithm의 의사코드이다. 

MST-PRIM(G, r)

   Q = V 

   for each u ∈ V[G] 

      do d[u] = INF

         tree[u] = NIL

   d[r] = 0  

   while Q != 0

      do u = EXTRACT-MIN(Q) ---- ①

         for each v ∈ Adj[u]

            do if v ∈ Q and w(u, v) < d[v]

                  then d[v] = w(u, v)

                       tree[v] = u

EXTRACT-MIN(Q){

   집합 Q에서 d값이 가장 작은 정점 u를 리턴하고, u를 집합 Q에서 제거한다.

}

위 의사 코드를 구현하고, 시작 노드 1에서 출발하는 MST를 구하면서 Output 조건에 맞게 출력하시오. 

Input

입력의 첫줄에는 노드의 수(n)과 간선의 정보 수(m)이 들어온다. 노드는 1부터 n까지 있다.

다음 m줄에는 간선을 이루는 노드(x, y)와 그 간선의 가중치 w가 들어온다.

Output

① 에서 추출되는 u를 순서대로 출력하고 마지막에 MST의 총 가중치의 합을 출력한다. 각 숫자는 빈칸으로 구분한다.

Sample Input

4 5

1 2 3

1 4 1

2 3 4

2 4 2

3 4 5

Sample Output

1 4 2 3 7

=================================================================

Kruskal

Contents

다음은 MST를 구하기 위한 여러 알고리즘 중 하나인 Kruskal's Algorithm의 의사코드이다. 

MST-KRUSKAL(G, w)

A = empty set

for each vertex v ∈ G.V

   MAKE-SET(v)

sort the edges of G.E into nondecreasing order by weight w

for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight

   if FIND-SET(u) != FIND-SET(v)

      total = total + w(u, v) --- (1)

      A = A ∪ {(u, v)}

      UNION(u, v)

return A

위 의사 코드를 구현하고, 조건에 맞게 출력하시오.

Input

입력의 첫줄에는 노드의 수(n)과 간선의 정보 수(m)이 들어온다. 노드는 1부터 n까지 있다.

다음 m줄에는 간선을 이루는 노드(x, y)와 그 간선의 가중치 w가 들어온다.

Output

MST의 총 가중치의 합을 출력한다.

Sample Input

4 5

1 2 3

1 4 1

2 3 4

2 4 2

3 4 5

Sample Output

7

=================================================================

Dijkstra

Contents

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

음의 가중치가 없는 단방향 그래프와 시작점과 도착점이 주어졌을 때, 시작점에서 도착점까지의 가장 최단 거리를 구하는 여러 알고리즘 중에 Dijkstra's Algorithm이 있다. 알고리즘의 의사 코드는 다음과 같다.

Dijkstra(G, r)

{

   S = empty; //S는 정점 집합

   for each u ∈V

      d[u] = INF

   d[r] = 0

   while(S!=V){

      u = extractMin(V-S, d); ---(1)

      for each v ∈ Adj(u)

         if(v ∈ V-S and d[u] + w(u, v) < d[v]){

            d[v] = d[u] + w(u, v);

            prev[v] = u;

         }

   }

   return d[t];   

}

위 Dijkstra 알고리즘을 구현하고, 조건에 맞게 출력하시오. 

※ 이완 조건(Relaxation condition)은 d[u] + w(u, v) < d[v]로 한다.

Input

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

Output

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다.

Sample Input

5 10 2

1 2 2

1 3 7

1 4 5

1 5 6

2 4 2

2 3 4

3 4 6

3 5 8

5 2 4

5 4 1

Sample Output

-1

10

7

5

14