7. 빨간 구슬 홀에 넣기 알고리즘 (재귀)

1. 개요

N*N의 맵에서 임의로 빨간 구슬과 파란 구슬, 그리고 몇 개의 구멍이 배치되어 있다.

여기서 빨간 구슬과, 파란 구슬은 위치는 달라도 같은 방향으로 함께 움직인다.

빨간 구슬이 구멍에 들어가면 성공, 파란 구슬이 들어가면 실패이다.

10번 이내에 찾을 수 있는 방법을 구하시오.

현재 방법은 모든 경우를 검사하는 Brute Force 기법으로 풀었으며, 한 개의 케이스에 0.4초쯤 걸린다.

즉, 이 방법으로는 절대 1초에 5개의 테스트케이스를 처리할 수 없다.

몇 가지 보완 방법이 있다.

동서남북 중 한 가지 길을 택했을 때 현재 거리가 지금까지 구한 최소 거리보다 길면 return하는 방식으로

조금 더 시간을 줄일 수 있겠지만 완벽한 풀이는 아닌 것 같다.

새로운 점화식과 아이디어를 도출하고 이를 어떻게 메모이제이션을 적용하고 DP를 적용할지 충분히 고민해보자.

시험 전까지 시간 내에 이를 완벽히 처리할 수 있는 알고리즘으로 보완하자.

Brute Force 점화식

빨간 구슬의 위치를 기점으로 동서남북으로 움직인다.

만약, 움직인 거리가 10을 초과하면 return.

파란 구슬이 홀에 위치하면 return.

위 두 조건을 피해 빨간 구슬이 홀에 위치하면 성공.

현재 위의 아이디어 적용 결과 하나의 케이스 당 0.1초로 줄었다.

그렇다면 충분히 5개의 케이스를 1초내에 풀 수 있다.

2. 문제

2차원 맵이 있고 벽으로 둘러싸인 공간이다.안에는 빨간 구슬 1개, 파란 구슬 1개와 하나 혹은 여러개의 ‘홀’이 존재한다.

목표부터 먼저 말하자면, 빨간 구슬을 홀에 넣기 위해 움직여야 하는 최소의 움직임 수를 구하는 것이다.

움직임은 상하좌우가 가능하다.

빨간구슬이 홀에 빠지면 성공이지만, 파란구슬이 홀에 빠지면 무조건 실패이다.

즉, 빨간구슬과 파란구슬이 동시에 홀에 빠지는 경우 실패이다.

구슬이 움직이려는 방향에 벽이 있다면 구슬은 움직이지 아니한다.

한번의 움직임은 빨간구슬과 파란구슬 동시에 적용된다.

각 테스트 케이스에 대해서  10번 이내에 움직여서 성공할 수 있는 최소의 움직임 수를 구해야 하며, 

만약 10번 이내에 절대 성공할 수 없다면 - 1을 출력한다.

테스트 케이스는 5개가 주어진다.

모든 테스트 케이스를 처리하는데 걸리는 시간은 1초(c, c++), 4초(자바)이내여야 한다. 

3. 코드

3-1) 구조체 및 함수선언

3-2) 메인 계산 함수

3-3) 초기 위치 설정 함수

3-4) 동서남북 재귀적으로 움직이는 move() 함수

3-5) 빨간 구슬 move() 함수

3-6) 파란 구슬 move() 함수

3-7) 출력 (개선 전)

 

3-8) 출력 (개선 후 - 개요에 쓴 아이디어로(간단한 메모)) 

4. 정리

여러 문제 속에서 그 문제의 진의를 꿰뚫자.

코드는 항상 모듈별로 간결하게. 그래야 논리적으로 꼬일 확률이 적다.

잘 안풀려도 최선을 다해서 포기하지말자. 

마음이 요동치기 시작하면 그 이후부터 작성한 코드는 이미 망가진다.

다시 심호흡하고 차분하고 냉정하게 재시작하자.

정말 미친듯이 일주일을 보내고 쉬는 것은 시험이 끝난 일요일 날 푹 쉬자.

흐우우우우우!!