CodeDrive

문제:

인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.

그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.

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

첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.

남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다. 남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.

경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다. 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.

보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.

입력:

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.

출력:

출력은 N 개의 줄로 이뤄지며, 한 줄에 하나의 번호를 출력한 다. 이들은 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다. 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다.

풀이방법:

 순서가 정해져있는 작업을 차례로 수행해야 할 때 순서를 결정해주는 문제이므로 '위상 정렬'을 사용해야 한다. 위상 정렬에 대한 설명은 다음 페이지에 설명이 잘 되어 있기에 링크를 달아두도록 한다.

https://m.blog.naver.com/ndb796/221236874984

 문제의 설명에서 '세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.' 라는 것이 있는데, 이는 위상 정렬을 수행할 때 사이클이 생기는 경우에 해당한다. 이러한 경우에 위상정렬을 하면서 순서를 정할 때, N명이 모두 순서가 정해지지 않게 된다.

 따라서 위상정렬을 하고 난 뒤에 길이가 N이 아니라면 -1을 출력하도록 한다.

문제링크:

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

문제:

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력:

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력:

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이방법:

 바이러스 번호가 낮은 것부터 2차원 배열에 확산시키는 문제로 너비 우선 탐색에 해당한다. 처음에는 시간을 고려하지 않고, 너비 우선 탐색만 생각하고 문제를 풀려고 했으나 계속해서 시간초과가 발생하게 되었다.

 처음 생각했던 방법은 중복으로 탐색하는 경우도 많았으며, 이미 다 채워져 있었는데 시간(S)이 남았다는 이유로 계속 2차원 배열 탐색을 계속했기 때문에 시간초과가 발생했던 것으로 보인다. 

 그래서 deque에 바이러스 종류, 시간, 좌표등을 모두 저장하고 이를 기준으로 바이러스를 증식시키는 것으로 수정하게 되었다. 초기 시험관을 받고 바이러스 정보를 모두 deque에 넣고 정렬하면 낮은 종류의 바이러스부터 먼저 증식시킬 수 있다.

문제링크:

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

문제:

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

입력:

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력:

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

풀이방법:

 한 번의 점프가 한 겹의 친구들을 쓰러뜨리고, 친구들을 쓰러뜨릴(?) 때 까지 반복한다는 것은 BFS를 반복적으로 사용한다는 것과 같다. 따라서 시작점으로부터 상하좌우로 BFS를 수행하도록 한다.

 여기서 한 번의 점프가 단순히 한번 상하좌우로 움직이는 것이 아니라 상하좌우로 모두 친구들을 쓰러뜨리는 것이다. 따라서 BFS를 탐색할 때, 친구가 있거나 초코바가 있다면 queue의 우측에 값을 넣도록 하고(다음 점프임을 의미), 그렇지 않다면 queue의 왼쪽에 값을 넣도록 한다(같은 점프 내에 쓰러져야함). visited 개념을 distance로 사용하여 몇 번째 점프인지 기록하도록 한다.

 이렇게 모든 점프를 마친 뒤에 초코바 위치에 있는 distance를 출력하도록 한다.

문제링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

풀이방법:

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

2022.08.09 - [Algorithm/Python] - [BOJ]12851. 숨바꼭질 2

 이전 문제의 발전된 버전으로 가장 빠른 시간과 그 시간으로 이동한 경로를 출력해야 하는 문제다. 위 문제 해결 방법에 추가적으로 visited 배열을 이전에는 0과 1의 여부로만 사용했지만 count 값을 저장하도록 하여 최소 시간을 측정할 수 있도록 했다. 그리고 path라는 배열을 사용해서 이동한 점의 위치에 기존에 있었던 점의 값을 저장하도록 하여, 동생이 위치한 점에 도달했을 때, 역추론이 가능하도록 한다.

 역추론을 하기 위한 print_path라는 함수가 존재하며 history를 만든 후 이를 뒤집어서 출력하도록 한다.

문제링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

풀이방법:

BFS를 사용하여 수빈이가 이동할 수 있는 거리내에서 동생이 있는 위치에 도달하는 시간을 측정하도록 한다.

수빈이가 이동할 수 있는 방법은 총 3가지이므로, 이동할 점이 가능한 범위 내에 존재하고 이전에 도달한 적이 없는 곳이라면 queue에 넣고 이동하도록 한다. 그러다 동생이 있는 위치에 도달하면 해당 시간의 count를 하나 증가 시키고, 모든 탐색을 마친 뒤에는 시간, count의 dict에서 최소 시간의 count를 출력하도록 한다.

문제링크:

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

문제:

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력:

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

풀이방법:

 맥주 한 박스에는 맥주가 20개 들어있고, 편의점에서 이를 채울 수 있다. 편의점에 도달하면 무조건 맥주를 가득 채우는 것이 이득이므로, 최대로 이동할 수 있는 거리는 1000미터다. 따라서 현재 있는 위치로부터 1000미터 이내에 편의점이 있거나 페스티벌을 하는 장소가 있는지 찾으면 된다. 

 따라서 페스티벌을 하는 장소에 도달하는지의 여부를 찾으면 되기 때문에 1000미터 이내에 도달할 수 있는 장소를 모두 저장하며 탐색하는 BFS 방법을 사용하도록 한다.

문제링크:

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

문제:

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력:

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

풀이방법:

 사이클이 존재하지 않고, 방향이 존재하는 그래프 상에서의 정렬을 해야 하는 문제이기 때문에 위상정렬을 사용해서 이 문제를 푼다. 

 위상정렬의 기본 알고리즘 진행은 다음과 같다.

1. 각 입력으로 들어온 값들을 그래프 형태로 저장한다. 이와 동시에 in_degree라는 간선이 연결된 갯수를 저장하는 배열도 같이 초기화 시킨다.

2. 모든 입력을 마친 뒤, in_degree가 0인 것부터 queue(deque)에 입력해 준다.

3. queue에서 값을 하나씩 빼면서 나온 노드들이 정렬된 것이며, 해당 노드와 연결되어 있는 선을 하나씩 제거한다.

3-1. 이 때, in_degree 값이 0이 된다면 queue에 넣는다.

4. 위 과정을 queue가 비어 있을 때까지 한다.

문제링크:

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

문제:

민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

입력:

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.

항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

출력:

첫째 줄에 문제 번호를 나타내는 1 이상 N 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.

풀이방법:

이 문제는 '사이클'이 없으며 '방향'만 존재하는 그래프에서 정점을 나열하는 방법으로 풀 수 있다. 이러한 문제 푸는 방법을 위상 정렬 (Topological Sort)라고 한다.

 또한 시간을 최소화하기 위해서 최소 힙을 사용한 우선순위 큐를 사용하도록 한다. 문제는 다음과 같은 알고리즘 순서로 해결한다.

1. 정점과 연결된 그래프와 해당 정점과 연결된 정점의 개수 리스트를 만든다.

2. 연결된 정점 개수 리스트(In_degree)가 없는 정점부터 먼저 최소 힙에 넣어준다.

3. 해당 정점과 연결되어 있는 정점(In_degree)들부터 하나씩 제거해 준다.

4. 연결된 정점 개수가 없는 정점이 생긴다면 최소 힙을 다시 넣어준다. 이후 3)으로 돌아간다.

문제링크:

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

문제:

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력:

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력:

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이방법:

 한 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘에는 다익스트라 알고리즘이 있다. 따라서 해당 문제를 다익스트라 알고리즘을 사용해서 풀었다.

 해당 문제에서 조심해야 하는 점은 출발 도시와 도착 도시가 한 쌍으로 주어지지 않는다는 것이다. 즉 A 도시에서 C 도시로 이동하는 버스가 여러번 입력으로 들어올 수 있다. 그러므로 입력을 받을 당시에 도시간에 이동하는 비용은 항상 최소가 되도록 유지시켜 준다.

 다익스트라 알고리즘은 heapq를 사용한 방법을 사용하여 구현을 했다.

문제링크:

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

문제:

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력:

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력:

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

풀이방법:

'친구사이'라는 용어가 애매하게 정의되어 있어서 헷갈릴 수 있지만 자신을 제외한 다른 모든 회원과 친구가 되기 위해 필요한 최대 거리를 의미한다. 즉 '친구의 친구의 친구'는 그 사람과 내가 알기 위해서 필요한 다리의 수와 같다.

따라서 이 문제를 플로이드-와샬문제로 생각하여 해결한다. 플로이드-와샬로 친구가 되기 위해 필요한 사람의 수들을 모두 구한 뒤, 각 사람마다 제일 큰 값이 그 회원의 점수가 된다.

회장이 될 수 있는 사람은 그 점수들 중 가장 작은 사람이여야 하기 때문에 그 점수들 중에 min을 찾은 후 그 점수를 가지고 있는 사람들을 출력한다.

문제링크:

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