9655. 돌 게임

5

SK

1. 접근

내가 상근이라면 현재 남은 돌의 갯수를 보고 어떤 선택을 내리는게 완벽한 플레이일까?

1개 남았다면 당연히 1개 가져가면 이긴다.

3개 남았다면 당연히 3개 가져가면 이긴다.

2개 남았다면 1개 가져가고 깨끗하게 지는게 매너플레이다.

4개 남았다면 무슨 짓을 해도 진다.

분명 남은 갯수와 승패에는 연관이 있는 것 같지만 일단 모든 경우를 생각해 보기로 하자.

2-1) 풀이 1

나나 상대나 두 가지 초이스를 할 수 있으므로 이차원 배열 dp[턴][남은 돌]을 정의해보자.

이 배열은 내가 이기는지 지는지 상태를 저장한다.

현재 dp[my][N] 이라면, 나는 1개나 3개를 가져간다. 턴은 상대에게 넘어가고, 그 경우에 내가 이길 수 있는 경우가

하나라도 있다면 나는 그 선택을 완벽하게 할 것이다.

반대로 현재 dp[your][N] 이라면 상대는 1개나 3개를 가져갈 수 있고, 턴은 내것이 될 것이고, 그 경우에 상대가 이길 수 있는 경우가

하나라도 있다면 상대는 그 선택을 완벽하게 할 것이다.

같은 말로, 내가 모두 이기는 경우만 남는다면 나의 승리다. 하나라도 상대가 이기는 경우가 있다면 상대의 승리다.

따라서 우리는 재귀적으로 경우를 확장시켜 보기로 하자.

dp[my][N] 부터 시작해서 dp[my][0], dp[your][0] 까지 확장시킨다.

한 케이스는 두 케이스로 분화된다. (1개를 가져가거나 3개를 가져가거나)

남은 돌이 0개인 채로 턴을 받으면  그 사람의 패배인 것이다.

2-1) 풀이 1. 코드

분화시키다보면 remain이 음수가 되버리는 경우가 있다(21행). 그 경우엔 논리식(31, 35행) 에 영향을 주지않는 값을 리턴해주기로 하자.

2-2) 풀이 2

베스킨라벤스 31 게임을 생각해보면 비슷한 이유로 승패가 갈린다.

우리는 초딩때의 경험으로 30, 26, 22, ... , 2를 먹으면 이긴다는 필승법을 알고 있다.

30을 먹으면 상대는 31을 먹고 질 수 밖에 없다.

30을 먹으려면 26을 먹어야 한다. 상대가 몇개를 먹건 나는 30을 먹을 수 있다.

26을 먹으려면 22을 먹어야 한다.

...

이는 한 번에 3개까지 먹을 수 있다는 게임의 특징에서 비롯된다.

마찬가지로 상대가 이길 수 없게 할려면 2개나 4개를 남겨주면 이긴다.

2개를 남기려면 내 턴에 3개나 5개여야 한다.

4개를 남기려면 내 턴에 5개나 7개여야 한다.

...

따라서 승패는 짝수 홀수에 따라 갈린다.

2-2) 풀이 2. 코드

3. 후기

이미 기록된 dp배열에 접근할 땐 기존 값을 리턴해주기로 했다. (코드의 28줄)

헌데 이 조건을 함수의 맨 처음에 두었더니 이상한 값이 리턴되었다. 먼저 기저를 작성하고 나중에 기존값 여부를 확인하자.

1. 세그먼트-트리(구간 트리)란?

세그먼트-트리(구간 트리)란 말 그대로 세그먼트(구간)를 저장하는 트리 자료구조다.

이 자료구조의 기능은 임의의 포인트를 어떤 세그먼트가 포함하고 있는지 반환해줄 수 있다.

또한 다음과 같은 구조를 갖는다.

1) 완전 이진 트리 (마지막 레벨을 제외하고 모든 노드는 자식을 두 개 갖는다.)

2) 트리의 잎들은 기본 간격들에 대응된다. 따라서 가장 좌단의 잎은 가장 처음의 기본 간격에 해당한다.

3) 내부 노드들은 기본 간격을 합친 간격에 대응된다.

따라서 두 잎을 자식으로 하는 내부 노드는, 두 잎에 해당하는 기본 간격을 합친 간격에 대응된다.

위와 같은 규칙으로 우리는 다음 기능들을 유추해 낼 수 있다.

1) n개의 간격이 있다면, 최대 4n + 1 개의 기본 간격이 있을 수 있다. 기본 간격은 잎에 대응된다.

그래서 이진트리의 잎이 4n + 1개 이므로, 높이는 O(log n)이다. 따라서 사용하는 공간은 O(n * log n)이다.

2) 루트 노드부터 1번, 왼쪽 자식은 2번, 오른쪽 자식은 3번, ... 식으로 번호를 매긴다면 다음이 성립한다.

부모 노드가 k번 이라면 왼쪽 자식은 2 * k 번, 오른쪽 자식은 2 * k + 1 번이다.

또한 n개의 기본 간격이 있다면, 총 노드 수는 2 * n - 1 개다.

2. 세그먼트-트리의 활용분야

세그먼트-트리의 강점은 높이가 log n 이라는 특징에서 비롯된다.

두 가지 질의를 하는 문제가 있다고 하자. (질의는 N번 주어진다.)

1) [from, to] 범위의 정보를 모두 구해라.

2) 기본 간격 A의 정보(a)를 b로 변경해라.

단순히 1번 질의를 O(N)으로 수행할 수도 있다.(1번 질의를 받을 때 마다 매번 구한다)

그러면 총 시간 복잡도는 O(N * N)이 될 것이다.

미리 [from, to]를 구하고 저장해둔다면 1번 질의를 상수시간에 해낼 수 있다.

하지만 2번 질의가 주어지는 순간, 미리 구해둔 정보 중 A와 관련된 모든 정보를 수정해야 한다.

따라서 최악의 경우 시간 복잡도는 동일하다.

하지만 세그먼트 트리는 위와 같은 질의를 높이에 비례해서 해낼 수 있다.

만약 1번 질의로 [1, 6]가 주어졌다고 하자.

루트는 현재 [1, 8]을 알고 있지만, 질의와 관계업는 정보도 갖고 있다. 따라서 왼쪽과 오른쪽 자식에게 세부 정보를 알아내야 한다.

왼쪽 자식(2번 노드)은 [1, 4]를 안다. 이는 질의의 일부분이다.

오른쪽 자식(3번 노드)은 [5, 8]을 안다. 하지만 질의와 겹치지 않는 부분이 있다. 다시 왼쪽, 오른쪽 자식에게 세부 정보를 알아내자.

3번 노드의 왼쪽 자식(6번 노드)은 [5, 6]을 안다. 이는 질의의 일부분이다.

3번 노드의 오른쪽 자식(7번 노드)은 [7, 8]을 안다. 이는 질의와 상관없는 정보다.

따라서 2번 노드와 6번 노드를 합치면 질의에 답할 수 있다.

2번 질의 또한 위와 유사한 과정을 통해 부모 노드들을 갱신시켜가면서 수행된다.

1번 질의와 2번 질의 모두 루트부터 시작된 트리 탐색으로 높이에 비례한 수행시간을 가진다.

따라서 세그먼트-트리의 위와 같은 질의에 대한 수행시간은 O(log n)이다.

3. 문제에 적용

정보 탐색과 갱신은 루트부터 시작된다.

탐색은 노드의 번호와 기타 정보를 통해 아래방향으로 진행된다.

하지만 갱신은 갱신 노드에 도달한 이후 윗방향으로 이루어진다. 따라서 재귀적인 코드가 직관적이다.

3-1) 백준 : 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042

코드 : 

3-2) 백준 : 10868 최소값 https://www.acmicpc.net/problem/10868

코드 : 

1944. 복제 로봇 

5 2
11111
1S001
10001
1K1K1
11111

6

1. 접근

S에서 시작해서 K로 가야한다. K에 도착하면 원하는 수만큼 자신을 복사할 수 있으며, 최종적으로 모든 K에 도착해야한다.

이 때 가장 적은 경로의 합을 구하는 문제다.

S와 K들 사이의 경로를 그래프처럼 그려보자.

예시 입력에는 2개의 K개 있으며 (K1, K2) S에서 K1으로 가는 비용은 2, K2는 4이다.

먼저 K1으로 가기로 해보고, 도착 한뒤 자아 분열을 통해 K2로 가는 비용은 4이다.

따라서 우리는 S와 K들 사이의 최소거리를 비용으로 하는 간선들로 이루어진 그래프로 문제를 이해할 수 있다.

그러면 문제에서 원하는 해답은 그래프의 어떤 모습이겠는가?

그래프를 최소신장트리화시켜 비용의 합을 원하는 문제임을 알 수 있다.

2. 풀이

최소거리를 먼저 구해서 간선화시키는 방법이 필요할 것이다. 이에 BFS를 차용한다.

매 S, K들 마다 BFS를 돌려서 간선들을 만들고 저장한다.

BFS시에 모든 K를 방문하지 못한다면 길이 없는 것이므로 -1을 출력한다.

그 후엔 디스조인트-셋을 활용한 크루스칼 알고리즘을 사용하면 된다.

키의 번호는 정해져 있지 않으므로, 각 좌표의 키 번호를 지정하고 저장할 배열이 필요할 것이다.

이후 저장된 간선들에 대해 정렬하고 크루스칼 알고리즘을 돌리자.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

2887. 행성 터널

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

4

1. 접근

모든 터널을 연결하는데 필요한 최소비용을 구하는 최소신장트리 문제이다.

크루스칼 알고리즘을 사용하자.

2. 풀이

간선을 고르는게 문제다.

A터널과 B터널의 연결은 x, y, z 좌표 중에 차이가 가장 작은 축으로 이루어진다.

단순히 N^2 으로 모든 터널을 만들어 본 다음에 크루스칼을 돌려볼 수 있지만, 시간제한이 문제다.

그러면 다음으로 떠오르는 생각은 정렬을 통해 N * log n 으로 해결할 방법을 찾아보는 것이다.

정렬이후 i, i - 1 행성의 차이로 터널을 만들어 보자. 그러면 총 3 * (N - 1) 개의 터널이 생길 것이다.

이 후 크루스칼을 돌리면 된다.

왜 이 방법이 최소신장트리의 모든 간선을 놓치지 않는 걸까?

단순히 x 축만 사용한다고 생각해보자. ( x = 0, 3, 4, 8, 13, 14 ) 

정렬 이후에 이웃 행성들 끼리만 터널을 만든다면 바로 0~14 까지 일렬로 쭈욱 터널이 생긴다.

바로 최소신장트리를 만들 수 있다. 이 간선들 외에 다른 최소신장 트리를 만드는 방법은 없다.

따라서 축을 세 개 쓴다고 해도 이는 변하지 않는다.

다만 쓸데 없는 간선이 2 * (N - 1)개 추가될 뿐이다.

정답인 N - 1 개의 간선은 놓쳐지지 않고 포함된다.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

9372. 행성 터널

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

2
4

1. 접근

번역이 좀 애매하게 되어있지만, 가장 적은 종류의 비행기란 결국 최소신장트리를 구하라는 뜻과 일맥상통한다.

원문에는 가장 기장을 적게 알게 되면서 모든 도시를 방문하는 기장 수를 출력하라고 되어있다.

비행기를 처음 타면 기장과 안면을 트게 되고, 다시 타도 알던 사이이므로 상관없다. 즉 간선을 가장 적게 포함하는 트리를 만들어야 한다.

2. 풀이

간선의 비용을 모두 같다고 해보자. 그러면 우리가 만들어야 하는 최소신장트리다.

허나 우리는 이미 최소신장트리의 간선 수를 알고 있다. n - 1 이므로 바로 출력해주자.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

1647. 도시 분할 계획

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

8

1. 접근

마을 안에 길이 너무 많아서 최소신장트리로 만들려고 한다.

단 마을을 둘로 나누고자 한다. 즉, 트리를 두개로 나누려고 하는 것이다.

최소신장트리이니 일단 크루스칼 알고리즘을 쓰기로 한다.

2. 풀이

일단 마을을 최소신장트리로 만들어보자.

그러면 길은 N - 1개일 것이다. 이 트리에서 간선을 하나 제거해서 한 집을 똑 떼어놓아 보자.

그러면 기존의 트리는 N - 2개의 길로 이루어졌고, N - 1개를 포함하는 최소신장트리이다.

당연히 떨어진 집은 자체로도 마을이고 최소신장트리이다.

그러면 제거할 간선의 기준은 어떻게 되겠는가? 트리 중 가장 큰 간선이다.

이 간선은 또한 크루스칼 알고리즘의 가장 마지막에 합류한 간선이다.

따라서 길을 N - 2개 까지만 크루스칼 알고리즘을 진행해도 같은 결과를 얻을 수 있다.

마을을 두개로 나누는 방법은 여러가지이지만, 간선의 수 (N-2) 는 동일하다.

따라서 가장 큰 간선을 제거하는 위의 방법이 최소임은 보장된다.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

1922. 네트워크 연결

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

23

1. 접근

최소신장트리를 구해야 한다.

http://js1jj2sk3.tistory.com/23와 동일하다.

크루스칼 알고리즘을 사용하자.

2. 풀이

사이클의 유무를 확인하는데 디스조인트-셋을 사용한다.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

1197. 최소 스패닝 트리

3 3
1 2 1
2 3 2
1 3 3

3

1. 접근

대놓고 최소스패닝트리를 찾으라고 써있는 문제.

크루스칼 알고리즘을 쓰자.

2. 풀이

간선들을 가중치 순으로 정렬하자.

가장 작은 간선부터 보면서 추가시 사이클이 생기지 않는다면 추가해 준다.

사이클의 유무는 디스조인트-셋 으로 확인해준다. 루트 노드가 같다면 연결되어 있다는 뜻이고, 추가하면 사이클이 생겨버린다.

가중치의 합만 구하면 되므로, 간선의 순서를 기억하지 않아도 좋다.

다음을 참고 : http://js1jj2sk3.tistory.com/22

3. 코드

4. 후기

구조체를 algorithm : sort에 적용시키는 방법을 기억해두자. 연산자 오버로딩이 필요하다.

1. 최소신장트리란?

트리는 그래프의 노드들과 모든 노드간의 관계를 나타내는 간선들로 이루어진다.

최소신장트리란, 당연하게도 신장트리들 중에 가장 작은 규모의 트리를 말한다.

신장트리란 주어진 그래프의 모든 노드를 포함하면서, 모든 노드간에 관계가 있는(경로가 있는) 트리를 말한다.

다만 사이클은 포함하지 않아야 한다. 

규모라는 의미는, 간선들의 크기와 수에 비례하는 척도다.

따라서 최소신장트리는 신장트리를 만드는 여러 경우들 가운데 간선들의 크기(비용)의 합이 가장 작은 경우를 말한다.(사이클 미포함)

2. 최소신장트리를 구하는 알고리즘

그렇다면 최소신장트리를 어떻게 구할 수 있을까?

먼저 대표적인 알고리즘으로 크루스칼 알고리즘이 있다.

크루스칼 알고리즘의 흐름은 다음과 같다.

1) 간선들을 비용이 작은 순으로 정렬한다.

2) 가장 작은 간선부터 신장트리로 포함시킨다.(단 포함시키면 사이클이 생겨버리는 간선은 포함시키지 않는다.)

3) 모든 정점이 연결되지 않았다면 2단계로 돌아간다.

3단계로 보아 모든 정점이 포함될 것은 자명하고, 2단계의 제약조건으로 보아 사이클은 생기지 않을 것이다.

따라서 결과물이 신장트리가 될 것은 분명하다. 하지만 그 신장트리는 가장 작은 신장트리인가?

크루스칼 알고리즘이 최소신장트리를 찾는다는 증명은 다음과 같다.

우리는 다음을 귀납적으로 증명할 것이다 :

"알고리즘의 2단계를 수행하고 난 뒤 골라진 간선들의 집합을 F라고 하면, 항상 F를 포함하는 최소신장트리가 있다"

1단계에선 F는 빈 집합이다. 당연히 F를 포함하는 신장트리가 있다.

2단계는 반복적으로 수행된다. 다음에 2단계가 수행되면서 간선 e가 포함된다.

(F+e) 이 집합을 포함하는 최소신장트리가 있음을 보여야 한다.

e는 정답인 최소신장트리의 간선일 수도, 아닐 수도 있다. 맞다면 잘한 것이나, 아닐 경우 문제가 있다.

e가 노드 a, b를 잇는 간선이라고 해보자. 또한 원래 정답인 최소신장트리 또한 a에서 b로가는 경로를 유일하게 갖고 있다.

헌데 e를 추가함으로써 (F+e)는 사이클을 갖게된다. 이는 규칙에 어긋나므로 e가 정답의 일부임을 증명하였다.

두 번째 알고리즘으로 프림 알고리즘이 있다.

크루스칼 알고리즘이 최소신장트리를 이곳 저곳 따로 완성시켜나가는 반면, 프림은 한 지점부터 확장시켜나가면서 완성시킨다.

1) 아무 노드나 시작점으로 정한다.(A)

2) 그 노드에 연결된 간선 중 비용이 가장 작은 간선(A-B)을 포함시킨다. 단 B는 지금까지 연결되지 않은 노드이다.

3) A, B 아무 노드나 정하고 2를 반복한다.

최소신장트리를 완성해 나가는 과정은 선형시간에 가능하다.(크루스칼의 사이클을 확인하는 과정은 디스조인트-셋으로 간소화된다)

시간을 잡아먹는 작업은 가장 비용이 작은 간선을 찾는 작업에서 비롯된다.

크루스칼은 처음에 모든 간선을 정렬해야 하고, 프림은 각 단계의 노드와 연결된 간선들을 정렬해야한다.

따라서 시간 복잡도는 다음과 같다. 

3. 최소신장트리를 구해야 하는 문제들

1) 1197 최소 스패닝 트리 : https://www.acmicpc.net/problem/1197

말 그대로인 문제.

풀이 : http://js1jj2sk3.tistory.com/23

2) 1922 네트워크 연결 : https://www.acmicpc.net/problem/1922

모든 노드를 연결하는 최소비용을 구해야 한다. 최소신장트리의 정의를 알고 있는지 묻고 있다.

풀이 : http://js1jj2sk3.tistory.com/24

3) 1647 도시 분할 계획 : https://www.acmicpc.net/problem/1647

그래프를 두 최소신장트리로 나누려고 한다. 최소신장트리의 간선 수는 (노드의 수(n) - 1)임을 생각해보자.

풀이 : http://js1jj2sk3.tistory.com/25

4) 9372 상근이의 여행 : https://www.acmicpc.net/problem/9372

가장 적은 종류의 비행기를 탄다 = 가장 간선의 수가 적은 트리는 ? = 최소신장트리

풀이 : http://js1jj2sk3.tistory.com/26

5) 2887 행성 터널 : https://www.acmicpc.net/problem/2887

최소신장트리를 구해야 하는 문제임은 명확하지만, 간선이 모호하게 주어졌다. 

풀이 : http://js1jj2sk3.tistory.com/27

6) 1944 복제 로봇 : https://www.acmicpc.net/problem/1944

어느 지점을 노드화 시키고, 간선의 비용은 어떻게 구할 것인지가 중요하다.

풀이 : http://js1jj2sk3.tistory.com/28

3780. 네트워크 연결

1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O

0
2
3
5

1. 접근

각 기업별로 서버를 갖고 있다. 서버는 네트워크로 연결될 수 있고, 네트워크에는 센터 서버가 있다.

따라서 현재 기업마다의 센터는 단일 네트워크이자, 센터 서버이다.

이제 네트워크들을 I 명령어로 연결하고자 한다.

I 1 2 라면, 센터 서버인 1서버와, 2서버를 연결한다. 주의할 점은 첫번째 서버는 반드시 센터 서버이고,

두번째 서버는 그 서버가 속한 네터워크의 센터 서버가 아닐 수도 있다.

또한 연결된 이후에는, 두 네트워크는 하나의 네트워크가 되며, 센터 서버는 두번 째 서버가 담당한다.

우리는 서버들을 노드로 표현할 수 있으며, 서버들의 종속관계를 간선으로 표현할 수 있다.

간선의 크기는 |i - j|(mod 1000)으로 지정된다.

이때 한 기업이 주어지면, 기업의 서버에서, 그 서버의 센터 서버까지의 경로의 길이 합을 구해야 한다.

그래프적인 방법으로 접근해보자.

2. 풀이

네트워크는 집합으로, 센터는 루트 노드로 생각한다면, 바로 디스조인트-셋을 사용할 생각이 든다.

센터노드는 하나이므로, 노드에서 나가는 간선은 최대 한개이기 때문이다.

하지만 문제는 길이 합을 구해야 하기 때문에, 매번 경로를 탐색한다면,

명령어의 수(200,000) * 최악의 경로(20,000)으로 시간초과가 날 것이다.

따라서 디스조인트의 연산을 활용하여, 연결 시 마다 네트워크의 종속관계를 갱신해주고, 길이도 갱신해보도록 하자.

연결을 담당하는 union()시 i는 기존의 센터이고, j는 새로운 센터가 될 서버이므로 매우 쉽게 연결과 길이 정의가 가능하다.

이제 find()가 길이 합을 계산해주는 역할을 해야 한다. find는 부모를 재귀적으로 따라가서 최종적으로 루트노드를 반환해주는 연산이다.

우리가 원하는 연산은 센터를 제외한 나머지 노드의 부모를 센터로 지정하고, 길이도 갱신해줘야 한다.

또한 x서버에서 센터까지 가는 경로는 유일하므로, find를 조금 바꿔주면 가능하다.

재귀적으로 루트노드 갱신을 해주는 원래 기능에, 길이 갱신만 추가하면 된다.

len[x] += len[parent[x]]

다음 예시로 어떤 동작을 해야하는지 알아보자.

I 1, 2

I 2, 3

E 1

위와 같은 경우에, union()을 두번 수행한 결과 1번 노드는 2번 노드를, 2번 노도는 3번 노드를 가리키고 있을 것이다.

이제 find(1)을 수행하면, 1번 노드는 3번 노드를 가리켜야 하고, 길이는 2번 노드의 것을 추가하여 갱신되어야 한다.

3. 코드

재귀를 알맞게 구성해내는 경험이 더러 필요하다.