23.04.13 파이썬 코딩 퀴즈#217 사라지는 발판(프로그래머스 스쿨)

이번 문제는 사라지는 발판이다.

게임 보드는 1X1 크기의 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 존재한다.

플레이어 A,B는 처음 발판이 있는 곳에서 시작하며, 각 턴마다 한번씩 상하좌우 발판이 있는 곳으로 이동해야 한다.

패자와 승자가 정해지는 경우는 2가지 이다.

1. 움직일 차례인데 상하좌우 어디로도 움직일 수 없는 경우 (주변에 발판이 없는 경우)

2. 만약 두 캐릭터가 같은 발판 위에 있을 때, A가 먼저 이동하여 B가 밟고있는 발판이 사라지게 되는 경우 A승리

게임 플레이는 항상 A가 먼저 시작하며, 양 플레이어는 언제나 최적의 플레이를 한다. 즉 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이한다. 즉 양 플레이어의 이동 횟수가 최대가 되도록 움직입니다.

위는 예실 그림으로 3X3 보드의 모든 칸이 발판이며, 각 플레이어는 (1,0) 과 (1,2)에 위치합니다.

위 예시에서는 A가 실수하지 않는다면 항상 이길수 있는 경우이다.

따라서 A는 이기는 플레이어이고 B는 지는 플레이어가 된다.

A가 이기는 이동의 예시는 위와 같다.

A가 이기는 경우에는 어떻게 움직여도 양 플레이어의 이동 합은 5가 된다.

제한사항에서 확인해야 할 점은 board이다. 0은 발판이 없음을 1은 발판이 있음을 나타낸다.

플레이어 A,B의 출발 좌표는 aloc, bloc 으로 전달된다. 

한가지 중요한 사실은 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있다.

입출력 예에서 알 수 있듯이 board가 1X1 인 경우도 존재한다.

 

이제 문제에 대해 다시한번 생각해보자.

이길 수 있는 플레이어는 언제나 이기는 플레이를 한다. 이 말의 의미가 무엇일까?

먼저 시작하는 플레이어는 A 이다. 즉 A의 첫번째 이동에 따라 승패가 결정 된다는 의미일 수 있다.

B를 살펴보면, B는 절대 A가 밟은 발판으로 움직이지 않는다. 그 이유는 그 다음 차례에 A가 다른 칸으로 이동하는 순간 밟고 있던 발판이 사라져서 패배하게 된다. 즉, 최대한 오래 살아남으려면 A의 위치와 멀리 떨어질 수 밖에 없다.

위 그림은 입출력 예 2 번을 도식화한 것이다.

A는 B에 최대한 다가가야 하며, B는 최대한 멀리 도망가야 한다.

이 경우에 A는 처음 (0,0) 또는 (2,0)으로 이동 가능하다. 만약 A가 (0,0)으로 이동하였다면, B는 (2,2)로 먼 위치로 이동해야 한다. 그 다음은 어디로 이동하든 하나의 길만 있고, 최종적으로 A는 (0,2)에 B는 (2,0)에 도달하게 된다.

이제 A의 차례 이지만, 이미 모든 발판이 사라졌기 때문에 A는 패배하게 되며, 이때 A,B의 이동 횟수의 합은 6이 된다.

반대의 경로도 마찬가지이다. 즉 입장이 바뀌게 되었다.

 

그렇다면 A는 도망을 가야하는 입장이며, B는 추격해야 하는 입장이다.

다시 이동을 살펴보자

1. A는 (0,0)으로 이동한다

2. B는 (0,2)로 이동한다.

3. A는 (0,1) 로 이동한다

4. B는 (0,1)로 이동하여 A와 같은 발판을 밟는다.

이제 A의 차례이지만 더이상 이동 가능한 발판이 없다. 따라서 A의 패배이며 A,B의 이동 횟수의 합은 4가 된다.

 

문제를 다시 정리하자면 

1. A가 이길 수 있는 경우가 있다면 A는 반드시 그 경로로 이동한다

2. 만약 A가 반드시 지는 경우라면 B가 이길 수 있는 최단거리를 계산한다.

 

그리고 승리/패배 조건을 살펴보자.

1. A와 B가 같은 발판에 위치한다면, 그 다음 차례의 플레이어가 무조건 승리한다.

2. 현재 차례에 움직일 발판이 없다면, 그 플레이어는 무조건 패배한다.

 

일단 최적의 이동법에 대해 조금 생각을 해보아야 한다.

과연 어떻게 이동하는것이 최적의 이동법인가?

만약, A 가 이기는 경우가 존재한다면 어떻게 그 방법을 택하여 이동할 것인가?

먼저 작성한 코드를 하나씩 살펴보자

solution()에는 특별한 내용은 없다. 다만 index error 를 방지하기 위해 확장된 보드를 준비하고, 그에 맞춰 a,b 의 시작 좌표값을 옮겨준 뒤, 바로 search()함수를 실행하게 된다.

이제 search()함수를 살펴보자.

먼저 현재 전달받은 turn 값을 이용하여 플레이어를 식별하고(짝수는 A, 홀수는 B), 거기에 맞춰 현재 위치를 계산한다.

그 다음 이동가능한 위치 nloc 을 채워준다.

만약 nloc 이 없는 경우라면 현재 플레이어의 패배이며, 이때 False 값과 더 이상 이동이 필요 없기때문에 0을 반환한다

그리고 현재 두 플레이어의 위치가 동일하다면, 현재 플레이어의 승리이고, 한 번 더 움직여야 하기에 True, 1 을 반환한다.

승패가 확인이 되지 않는다면 flag 를 False 상태로 두고 보드 탐색을 시작한다.

이때 flag의 역활은 바로 현재 플레이어의 승리 가능성을 의미한다.

그리고 재귀로 실행된 board의 현재 위치 좌표값은 0으로 변환해 주고, 다시 최종적으로 그 값을 1로 반환해 준다.

이는 다음에 실행될 함수에서 현재 board에서 출발 시키기 위함이다.

이게 무슨 말인지 그림을 통해 살펴보자.

위는 입출력 예 1번을 시뮬레이션 한 모습이다.

먼저 A는 3개의 이동 루트를 가지며, A 이동에 관계없이 B 역시 3개의 루트를 가진다.

 

1번 루트는 아래와 같다

만약 A가 (0,0) 으로 이동한 상황을 먼저 가정해 보면, 먼저 B 가 (0,2) 로 이동하게 되면 둘은 (0,1)에서 반드시 만난다.

이 때, A 가 먼저 진입하므로 A의 승리이다. 따라서 총 이동 횟수는 5회가 된다. 이유는 겹쳐진 순간, 그 발판을 없애기 위해 A가 한번 더 움직여야 하기 때문이다.

 

2번 루트는 A(0,0),B(1,1)로 이동한 경우이다.

A 는 다음 이동은 (0,1)로 강제되며, B의 경우 2가지 방향으로 이동 가능하다.

만약 B 가 (0,1)을 택한다면 두 플레이어가 겹쳐지므로 다음턴인 A의 승리이고, 그렇지 않고 (2,0)으로 이동 한다면 최종적으로 B의 승리가 된다.

 

만약 해당 재귀함수 실행 후 현재 위치값을 1로 변환해주지 않는다면?

이미 1번 루트에서 몇개의 값들이 0으로 바뀌었기 때문에 2번 루트의 결과값은 달라진다.

즉 위로는 움직일 수 없기 때문에 실제로 이동 가능한 구역이 제한되게 된다.

따라서 최종적으로는 한번의 움직임으로 경기의 결과가 끝나는 경우가 발생한다.

 

이제 다시 남은 코드들을 살펴보자.

함수의 실행 결과는 flag(승패 가능성) 과 그에 따른 이동 횟수이다.

만약 result 가 False 인 경우라면, 현재 차례의 플레이어의 승리를 의미한다. 그 이유는 그 다음에 실행된 함수에서 False 값을 받았기 때문이다. 즉 다음 차례의 플레이어의 패배이다.

그렇다면 이때의 flag는 True 로 변환해 주고, 다음 이동까지 계산한 cnt+1 값과 현재 min_turn 값중 최솟값을 min_turn 에 저장해 준다.

만약 not flag 즉, 현재 승리가 확실하지 않은 경우라면, 현재 max_turn 값과 cnt+1 값중 최대값을 max_turn 에 저장하면 된다.