CodeDrive

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

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

문제:

유진이가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.

이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.

예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다

랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 송유진의 새로운 점수가 주어진다. 이때, 송유진의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오. 만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다면 -1을 출력한다.

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다. (예제 2)

입력:

첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 기존에 있던 중복된 숫자가 있을 수 있는데, 이를 새로 들어오는 숫자와 구분을 할 수 있어야 하는 문제다. 이를 구분하기 위해서 기존에 있던 숫자들에게 인덱스를 부여했으며, 새로 들어오는 숫자는 가장 큰 인덱스를 가지도록 하게 한다. 이렇게 하면 새로 들어오는 숫자가 기존에 있던 점수와 동일한 것이 있으면 그 뒤에 배치되게 된다.

 새로 정렬을 마친 뒤에 앞에서부터 P개 자르고, (새로 들어온 숫자, 인덱스)가 그 배열에 있다면 등수를 찾아 출력을 하고, 그렇지 않다면 -1을 출력하게 한다.

 또한 N이 0일 경우도 존재하게 되는데, 이 때는 두번째 줄을 입력받지 않아야 한다. 따라서 따로 예외처리를 해주어 빈 리스트를 정의하게 하도록 한다.

문제링크:

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

문제:

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력:

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력:

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이방법:

 자두가 움직일 수 있는 횟수는 W로 초는 T로 고정되어 있기 때문에 열은 W이고, 행은 T인 DP 테이블을 만들어서 이 문제를 해결하도록 한다.

 계속해서 움직이지 않는 경우는 1에서만 점수가 오르기 때문에 1일때만 이전 행의 0열 값을 가져와 1을 더하도록 한다. 1번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 짝수일 때 카운트가 오르게 되고, 2번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 홀수일 때 카운트가 오르게 된다. (1번나무에서 초기에 위치하기 때문)

문제링크:

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

문제:

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력:

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력:

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

풀이방법:

N명이 있을 때, 발생하는 경우의 수를 점화식으로 구하면 DP[N] = DP[N-1]+DP[N-2]와 같이 구할 수 있다.

그리고 VIP들 같은 경우에는 움직이지 못하기 때문에 주위 사람들과 자리 변경이 불가능하다. 따라서 양 옆을 분할한다라고 생각할 수 있다. 즉 문제에서 소개한 예시로 보면 9개의 자리가 있을 때, 4와 7에서 자리를 분할하고 있다. 이제 이 문제는 DP[3] * DP[2] * DP[2]와 같이 경우의 수를 구하면 된다.

문제링크:

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

문제:

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

풀이방법:

 처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.

 하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.

따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다. 

우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.

N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)

이를 정리하면 다음과 같이 표현할 수 있다.

N = LX + (1+2+3+...+L-1)

   = LX + (L-1)L/2

그럼 X는 다음과 같이 구할 수 있다.

X = N/L - (L-1)/2

따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.

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

문제:

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력:

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력:

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

풀이방법:

1. 우선순위 큐를 사용해서 연료 내에서 움직일 수 있는 주유소에서 주유하도록 한다.

2. 데이터를 전처리할 때, 거리는 작은 순으로 주어지지 않는다. 정렬이 필요하다

3. 마을에 도착하지 못하는 경우는 while에 있지만 더 이상 움직이지 못할 때를 의미한다. (candidates가 비어있는 경우)

문제링크:

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

문제:

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력:

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력:

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

풀이방법:

 가지고 있는 수 K 보다 사용해야 하는 갯수 N이 더 크면 가장 큰 숫자를 여러번 사용하는 것이 큰 수를 만드는데 유리하다. 따라서 가장 큰 수를 찾은 뒤에 N-K개 만큼 배열에 추가적으로 넣어준다.

 큰 수를 만들기 위해서는 두 수를 앞 뒤로 붙여보면 된다. 예를 들어 100 과 9 두 숫자가 있다고 했을 때, 큰 수가 무조건 가장 앞으로 오게 한다면 1009를 생성하게 되지만 실제로 큰 수는 9100가 되어야 한다. 따라서 1009 vs 9100과 같이 두 수를 번갈아 붙여보며 큰 수를 찾는 방법을 사용해야 한다. 

 따라서 python의 sort의 key 기능을 사용하며, 특수한 함수를 기준으로 정렬을 해야 하기 때문에 cmp_to_key를 사용하도록 한다.

문제링크:

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

문제:

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력:

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

풀이방법:

 치킨집들 중에서 임의의 M개의 치킨집을 골라 폐업시킨 뒤, 도시의 치킨 거리를 구한다. 그리고 이 과정을 가능한 모든 조합에 대해서 수행하고, 그 중 가장 최솟값인 도시의 치킨 거리를 출력한다.

 처음 입력을 받을 때 치킨집과 집과의 치킨 거리를 계산을 하고, itertools를 사용해 모든 폐업 조합(남아 있는 집)을 구한다. 남아 있는 집에 대해서 사전에 구했던 치킨 거리들을 합산함으로써 답을 얻는다.

문제링크:

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

문제:

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력:

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

풀이방법:

 bfs를 사용하여 각 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역들의 넓이를 구한다. 전체 영역을 1로 초기화하고 직사각형의 꼭짓점을 입력값으로 받을 때, 내부 영역들을 0으로 재정의한다.

 이 과정을 모두 마친 뒤, (0,0)부터 bfs를 사용하여 분리된 영역들의 각 넓이를 구한다. 한 점으로부터 시작해 이동하면서 visited를 업데이트하여 중복적으로 이동하는 것을 막으며 더 이상 이동하지 못할 때, 하나의 분리된 영역의 넓이를 구한 것으로 파악한다.

 탐색하는 과정을 region이 1이고, 방문하지 않은(visited가 0인) 곳에 대해 반복적으로 BFS를 수행하고, 이 결과들을 출력한다.

문제링크:

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

문제:

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력:

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력:

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

풀이방법:

 이 문제의 핵심은 물과 고슴도치의 이동을 BFS로 확인하면서 고슴도치가 비버의 집까지 갈 때까지 물의 영향을 받지 않는 지 확인해야 한다.

 우선 물에 대해서 BFS를 수행하면서 한 번 퍼질 때마다 1씩 늘어나면서 visit 배열이 채워진다. 이 때, 벽이나 비버의 집에는 물이 차지 않도록 한다.

 그 다음에는 고슴도치의 이동에 대해서 BFS를 수행하며 배열 안에 존재하며 비버의 집을 찾을 때 종료되도록 한다. 고슴도치가 이동할 때에는 물이 퍼진 정도에 따라 이동을 할 수 있으며, 물의 visit 배열 값보다 작을 때에만 이동할 수 있다. (물의 값이 4, 고슴도치가 이동할 값이 5라면 이동 불가 -> 물이 이미 차 있기 때문)

문제링크:

www.acmicpc.net/problem/3055