주간 문제풀이 02 (백준 1704 / 2645 / 22344 / 15972 / 10129)

P5 - 붕어빵타이쿤

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

1704번: 붕어빵타이쿤

문제: boolean 2D array가 주어지고, 한 점을 누르면 그 점과 상하좌우 4개 점의 값이 같이 반전된다. 점을 최소한으로 누르면서 배열을 모두 0으로 만드는 방법을 찾자.

풀이:

가장 위 행의 누르기 배치를 고정했다고 하자. 해당 배치로 인해서 가장 위 행의 배열 값이 1이 된 경우, 이를 보정할 수 있는 방법은 첫번째 행에서 1인 열에 해당하는 칸들을 두번째 행에서 눌러주는 것이다. 즉, 가장 위 행의 누르기 배치만 확정하면 그 아래 행들을 어떻게 눌러야 할지는 이미 고정이라는 것이다. 이 누르기 배치가 실제로 가능한지는 가장 아래 행(=보정할 수 없는 행)에서 1이 나타났는지를 보면 되고, 가능한 배치 중 가장 뒤집는 칸이 작은 배치를 찾으면 된다.

 

코드: http://boj.kr/6a24b4f253ef4ab8b2fc87b5b67aaa97

 

P4 - 회로배치

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

2645번: 회로배치

문제: N^2 그리드에서 A에서 B로 가는 최단경로를 찾는데, 이미 회로가 배치된 칸을 지나갈 때는 비용이 K이고, 배치되지 않은 칸은 1이다.

풀이:

특별한 게 없는 문제다. 회로가 점유하고 있는 칸을 기록하고, 이걸 이용해서 다익스트라를 돌리면 된다.

 

출력에서 최단경로를 구성해서 출력해야 하고, 출력 형식이 일반적이지 않음에 유의하자.

 

코드: http://boj.kr/d2a9b482d10446dda5d9eb6979daa6ca

 

P3 - 그래프 균형 맞추기

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

22344번: 그래프 균형 맞추기

문제: 간선 가중치가 있는 그래프가 있고, 각 노드에 가중치를 설정해 하여금 각 간선에 연결된 두 노드의 가중치의 합이 간선의 가중치의 합과 같도록 해야 한다. `조건을 만족하며 가중치를 부여하는 것이 가능한지`와, 가능하다면 `노드 가중치의 절대값의 합이 최소화되는 방안`을 찾아야 한다.

 

풀이:

그래프는 연결 그래프임이 주어져 있음으로, 임의의 spanning tree를 쉽게 구할 수 있다. spanning tree에 속해 있지 않은 간선을 우선 무시해보자. 루트 노드의 가중치를 x라고 했을 때, 트리를 dfs로 순회하면서 나머지 노드의 가중치를 모두 ax + b (a = 1 or -1)의 꼴로 표현할 수 있다.

 

이제 spanning tree에 속해 있지 않은 간선을 다시 고려하자. 임의의 spanning tree 밖의 간선에 대해서, 해당 간선이 연결하는 두 노드의 가중치를 합치면 다시 ax + b꼴로 표현할 수 있는데, 이 값이 해당 간선의 가중치와 같아야 한다. 이 제한을 통해서 x의 값을 유일하게 확정지을 수 있고, 불가능 판정이 될 수도 있다.

 

다만 이 과정 중에서 x의 값을 유일하게 확정지을 수 없었다면(ex. 주어진 그래프가 트리라서 spanning tree밖의 간선이 없었다면), x는 sum(|a_i*x+b_i|) 의 min값이 되어야 한다. (a_i = 1 or -1 이기 때문에) 이 문제는 각 |a_i*x+b_i|의 최소점을 모두 모아, 그 최소점들의 중간값을 찾으면 풀 수 있다.

 

코드: http://boj.kr/fcd9fdad9d29457da427d9231d0eeb11

 

P2 - 물탱크

 

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

15972번: 물탱크

문제: N*M 개의 격자 칸으로 이루어진 물탱크가 있고, 각 칸 사이 또는 외벽에 물을 흘려 보낼 수 있는 구멍이 특정 높이에 뚫려 있다. 물을 최대 높이 H까지 채운 후 물을 풀었을 때, 각 칸에 최종적으로 남아있는 물의 양의 합을 구하자.

 

풀이:

우선, 예를 들어서 외벽에 뚫려 있는 높이 h(<H)의 구멍은 하여금 그 구멍에 연결되어 있는 칸의 최대 높이를 h로 만든다. 여기서 이 최대 높이가 h으로 고정된 칸 옆으로 가는 구멍에 대한 두 가지 경우를 생각해 볼 수 있다.

- 옆으로 가는 구멍이 h보다 높은 h_high에 나 있다면, 그 옆으로 연결된 칸의 높이의 최대값은 h_high가 된다

- 옆으로 가는 구멍이 h보다 낮은 h_low에 나 있다면, 그 옆으로 연결된 칸의 높이의 최대값은 h가 된다 (직관적인 설명: h까지는 물의 압력차에 의해서 빠지게 되어 있는데, h가 된 다음부터는 압력차가 없음)

 

각 노드마다 인접한 노드을 보면서 최대값을 설정하는 개념은 그래프 탐색 시 사용하는 relax의 개념과 비슷하다는 것을 발견할 수 있다 -  단지 물의 높이를 일반적인 그래프 탐색 알고리즘의 거리와 같은 개념으로 생각하면 된다. 즉 그래프 탐색 알고리즘으로 거리를 찾듯이 각 칸의 최대 높이를 구할 수 있다.

 

시간 복잡도 안에 들기 위해서는 다익스트라를 쓰면 된다.

 

http://boj.kr/7229248f4c2e4292ae3018438fde8ea2

 

P1 - 작은 새

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

10129번: 작은 새

문제: N개의 높이가 있는 나무가 일렬로 있고, 새가 시작부터 끝까지 날아간다. 단 한번에 K개의 나무만 건너뛸 수 있고, 건너뛰면서 높이가 높아진다면 피로감을 느낀다. 이 때 피로감을 느끼는 횟수를 최소화하고자 한다.

 

풀이:

쿼리가 있긴 하지만, 각 쿼리별로 독립적으로 O(N)에 풀기만 하면 충분하다.

 

이를 위해서는, i번 위치까지 가기 위해서 피로감을 느끼는 가장 적은 회수를 dp[i]라고 하고 dp를 풀어보자. i번 위치에서의 dp값을 구하기 위해서는, (i-K)~(i-1) 범위에서의 가장 작은 dp값을 가져오는 것만으로는 충분하지 않아 보일 수 있다.(높이라는 요소가 있음으로) 하지만 dp는 한 번에 최대 1씩만 증가함으로, 범위 내에 가장 작은 dp값의 위치가 여러 개 있을 때 그 중에서 높이가 가장 높은 위치를 선택하는 것이 최적의 transition임을 어렵지 않게 알 수 있다. (the proof is left as an exercise..)

 

이제 문제는 i를 늘려가면서 (i-K)~(i-1) 구간에서의 make_pair(dp, -h)의 최소값 위치를 찾는 것인데, 이것은 priority queue를 쓰면 Nlog(N)이겠지만, 흔히 Monotone Queue Techinque이라고 부르는 기법을 사용하면 O(N)에 구할 수 있다.

 

코드: http://boj.kr/270fef4317824416bc61f2692ea19086