문제 링크

https://programmers.co.kr/learn/courses/30/lessons/92345

예상 난이도

G1

알고리즘 분류

게임 이론, 백트래킹

풀이

어떻게 보면 그냥 백트래킹을 잘 하면 되는 문제라고 말할 수 있지만 사실 게임이론/인공지능 등의 교과목을 들어서 Minimax Tree에 대해 알고있었거나 재귀와 백트래킹에 아주 친숙한게 아니었다면 현실적으로 풀어내기는 어려웠던 문제였습니다. 구현에서 실수할 여지가 너무 많아서 문제지 백트래킹 구조 자체는 저기 적힌 것처럼 간단합니다. solve 함수는 현재 상황에서의 답, 즉 현재 상황 이후로 두 캐릭터가 움직인 횟수의 총 합을 반환합니다.

이 문제의 상황 자체가 Minimax Tree와 동일하기 때문에 Minimax Tree에 대한 설명을 먼저 진행하는게 바람직하지만 Minimax Tree를 아예 처음부터 다 설명하기에는 좀 벅찹니다. 사실 이 문제는 만점방지용 문제라는 느낌이 좀 강하게 들긴 하지만 정말 꼭 풀이를 이해해보고 싶다고 하면 Minimax Tree를 개인적으로 공부한 후 계속 진행해주세요.

코드(C++)

앞에서 보여드린 pseudo code에서는 함수의 인자로 A가 움직일 차례인지 여부를 보냈지만 사실 이 문제에서는 A와 B가 완전히 같은 상황, 같은 전략으로 게임을 플레이하기 때문에 A와 B를 구분하지 말고 그냥 함수가 현재 플레이어의 좌표/상대 플레이어의 좌표를 인자로 받도록 둬도 됩니다. 재귀가 늘 그렇듯 매우 헷갈리겠지만 하노이 탑을 이해할 때와 마찬가지로 함수를 끝도 없이 따라들어가려고 하지 말고 귀납적인 사고로 잘 받아들여보시길 바랍니다.

코드(Python)

코드(Java)