Show tony.mb많은 개발자들이 카카오 플랫폼 서비스를 이용할 수 있도록 카카오 SDK를 개발하고 있습니다. 태그
지난 2021년 9월 11일 토요일 오후 2시부터 7시까지 5시간 동안 문제는 작년과 마찬가지로 쉬운 난이도에서 어려운 난이도 순으로 배치했습니다. 6번 문제를 제외한 나머지 문제는 테스트 케이스를 모두 통과해야 정답으로 인정되었고, 부문 점수는 부여되지 않았습니다. 6번 문제에는 효율적인 풀이를 구현해야 통과되는 효율성 테스트를 추가했고, 효율성 테스트는 정확성 테스트와 별도의 점수가 부여되도록 배점을 설계했습니다. 그럼 각 문제들을 살펴보고 해설을 진행하겠습니다. 문제 1 – 신고 결과 받기
문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
다음은 전체 유저 목록이 [“muzi”, “frodo”, “apeach”, “neo”]이고, k = 2(즉, 2번 이상 신고 당하면 이용 정지)인 경우의 예시입니다.
각 유저별로 신고 당한 횟수는 다음과 같습니다.
위 예시에서는 2번 이상 신고당한 “frodo”와 “neo”의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.
따라서 “muzi”는 처리 결과 메일을 2회, “frodo”와 “apeach”는 각각 처리 결과 메일을 1회 받게 됩니다. 이용자의 id가 담긴 문자열 배열 제한사항
입출력 예
• 입출력 예 #1 문제의 예시와 같습니다. • 입출력 예 #2 “ryan”이 “con”을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 “con”은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, “con”과 “ryan”은 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다. 문제 풀이 이 문제는 해시 자료구조를 활용할 수 있는지 묻는 문제였습니다. report를 하나씩 처리하면서 각 유저가 누구에게 신고를 당했는지 목록을 만듭니다.
유저 아이디는 최대 1,000개, report의 길이는 최대 200,000이므로 신고된 유저 아이디를 배열에 관리한다면 최악의 경우 O(아이디 개수 * report의 길이) 만큼의 시간이 걸립니다. 따라서 신고된 유저 아이디를 해시(또는 연관 배열) 자료구조를 이용해 관리하면 효율적으로 목록을 완성할 수 있습니다. 이때, 신고한 유저 목록에는 같은 아이디가 중복되어 들어가지 않도록 주의해야 합니다. 위와 같이 목록을 만들었다면 신고된 유저 아이디를 순회하면서 정지 기준을 만족하는 유저가 있다면(신고한 유저 수가 k 이상이면) 신고한 유저 목록을 순회하면서 메일을 보냈다는 표시(카운트를 1 증가) 해주면 됩니다. 문제 2 – k 진수에서 소수의 개수 구하기
문제 설명 양의 정수
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. 211은 정수
입출력 예
입출력 예 설명 • 입출력 예 #1 문제 예시와 같습니다. • 입출력 예 #2 110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다. 소수 판별하는 데에는 대표적으로 2가지 방법이 있습니다. 첫 번째로 에라토스테네스의 체가 있고, 두 번째는 어떤 수 n을 2부터 루트(n)까지 나눈 나머지가 모두 0이 아님을 확인하는 방법이 있습니다. 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 사용해서도 풀 수 있지만, 이 문제에서는 두 번째 방법으로도 충분히 해결할 수 있습니다. 이 문제의 제한사항을 살펴보면 n이 1부터 1,000,000까지이고 k는 3부터 10까지이므로, 1,000,000을 3진수로 바꾸면 1,212,210,202,001입니다. 일반적으로 진법 변환은 문자열을 사용해 구현하므로, 진법 변환된 문자열을 0을 기준으로 파싱 한 후에 소수를 판별하는 과정에서 정수 자료형으로 변환이 필요하게 됩니다. 이때, 개발 언어에 따라서 int 자료형의 표현 범위를 벗어날 수 있음을 유의해서 문제를 풀어야 합니다. 예를 들어 997,244를 3진수로 바꾸면 1,212,122,221,222가 됩니다. 이 숫자는 0이 없기 때문에 진법 변환된 숫자 그대로 정수 자료형으로 변환해서 소수 판별을 해야 하는데, 이는 int 자료형의 표현 범위를 벗어난다는 것을 알 수 있습니다. 문제 3 – 주차 요금 계산
문제 설명 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.
주차 요금을 나타내는 정수 배열
• 입출력 예 #1 문제 예시와 같습니다. • 입출력 예 #2
• 입출력 예 #3
이 문제는 문자열 처리 능력과, 주어진 주차 요금표를 코드를 통해 정확히 구현할 수 있는지를 확인하는 문제였습니다. 특히, 이 문제는 입/출차 시각과 누적 주차 시간을 모두 ‘분’단위로 환산하여 저장하면 조금 더 쉽게 해결할 수 있습니다. 차량번호의 범위가 0000~9999이므로, 차량의 수는 최대 1만 대입니다. 이를 이용하여 두 배열 in_time, total_time을 다음과 같이 정의합니다.
그 후 records에 담긴 원소를 순차적으로 처리해 줍니다.
records를 모두 처리한 후에도 출차되지 않은 차량이 있다면, 즉,
문제 4 – 양궁 대회
문제 설명 카카오배 양궁대회가 열렸습니다. 1. 어피치가 화살
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다. 현재 상황은 어피치가 화살 화살의 개수를 담은 자연수
• 입출력 예 #1 어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
어피치의 최종 점수는 15점, 라이언의 최종 점수는 19점입니다. 4점 차이로 라이언이 우승합니다. 하지만, 라이언이 아래와 같이 화살을 맞힐 경우 더 큰 점수 차로 우승할 수 있습니다.
어피치의 최종 점수는 17점, 라이언의 최종 점수는 23점입니다. 6점 차이로 라이언이 우승합니다. 따라서 • 입출력 예 #2 라이언이 10점을 맞혀도 어피치가 10점을 가져가게 됩니다. • 입출력 예 #3 어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
어피치의 최종 점수는 10점, 라이언의 최종 점수는 39점입니다. 29점 차이로 라이언이 우승합니다. 하지만 라이언이 아래와 같이 화살을 맞힐 경우,
어피치의 최종 점수는 13점, 라이언의 최종 점수는 42점입니다. 이 경우도 29점 차이로 라이언이 우승합니다. 하지만, 첫 번째 경우와 두 번째 경우를 비교했을 때, 두 번째 경우가 두 경우 중 가장 낮은 점수인 4점을 더 많이 맞혔기 때문에 • 입출력 예 #4 여러 경우 중에서 가장 낮은 점수를 가장 많이 맞힌, 10~3점을 한 발씩 맞히고 나머지 두 발을 0점에 맞히는 경우인
이 문제는 완전 탐색, 구현 문제입니다. 이 문제는 DFS, 비트 마스킹, 중복조합 등등 다양한 방법으로도 풀이가 가능한데요, 가장 많은 풀이가 나온 DFS를 이용한 완전 탐색으로 풀이를 진행하겠습니다. 이 문제를 해결하기 위해서는 각 점수를 아예 안 맞추거나 어피치보다 1발을 더 맞히는 경우로 각 점수(10점 ~ 0점)마다 2가지(총 2048가지)를 완전 탐색하면 됩니다. 예를 들어, 어피치가 만약 10점부터 0점까지를 0발부터 n발까지 하나씩 증가시키면서 완전탐색한다면 최악의 경우 시간 초과가 발생할 수 있는 점 유의하시길 바랍니다. 중복 조합으로 푸는 경우에도 10점부터 0점까지(11가지의 경우) 총, 10발의 화살을 쏘는 게 되기 때문에 11H10 = (11 + 10 – 1) C10 = 20C10 = 184,756으로 모든 경우의 수를 확인하면서 충분히 제한 시간 안에 문제를 해결할 수 있습니다. 문제 5 – 양과 늑대
문제 설명 2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수 보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다. 예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한 마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 모든 노드에는 늑대가 있고, 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다. 각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열
입출력 예 설명 • 입출력 예 #1 문제의 예시와 같습니다. • 입출력 예 #2 주어진 입력은 다음 그림과 같습니다. 0번 – 2번 – 5번 – 1번 – 4번 – 8번 – 3번 – 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.
4번 문제와 마찬가지로 이 문제 역시 다양한 방법으로 해결할 수 있는 문제인데요, 가장 많은 풀이가 나온 DFS를 이용한 완전탐색으로 풀이를 진행하겠습니다. 이 문제는 현재 위치, 현재까지 모은 양의 수, 늑대의 수, 그리고 다음으로 방문할 수 있는 노드 정보를 적절히 관리해 주면서 DFS를 이용해 완전탐색해서 해결할 수 있습니다. DFS를 수행하는 함수의 파라미터는 다음과 같이 구성할 수 있습니다.
현재 방문한 노드에 양이 있다면 양의 수를, 늑대가 있다면 늑대의 수를 1 증가시킵니다. 이때, xor 연산을 활용하면 아래와 같이 간단하게 구현할 수 있습니다. 현재 위치를 cur이라고 했을 때 현재 위치에 양이 있다면(info[cur]가 0인 경우) sheep에는 1이 더해지고, wolf에는 0이 더해집니다. 만약 늑대가 있다면 (info[cur]가 1이라면) sheep에는 0이 더해지고, wolf에는 1이 더해집니다.
다음으로 양의 수와 늑대의 수를 비교합니다. 만약 늑대가 양보다 많다면 현재 노드를 방문하는 것은 불가능하므로 더 이상 탐색하지 않습니다. 양의 수가 늑대의 수보다 더 많다면 모은 양의 최댓값을 갱신하고, 현재 노드의 자식 노드들을 다음으로 방문할 수 있는 노드 집합에 추가합니다. 이제 ‘다음으로 방문할 수 있는 노드의 집합’에 들어있는 모든 노드를 하나씩 방문하며 DFS 탐색을 수행합니다. 이 때, 다음으로 방문하는 노드의 번호를 ‘다음으로 방문할 수 있는 노드의 집합’에서 제거해 주어야 합니다. 이러한 방식으로 완전 탐색이 종료되면 최대로 모을 수 있는 양의 수를 구할 수 있습니다. 문제 6 – 파괴되지 않은 건물
문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다. 적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다. 첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다. 두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다. 세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다. 마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해 주세요.) 최종적으로 총 10개의 건물이 파괴되지 않았습니다. 건물의 내구도를 나타내는 2차원 정수 배열
효율성 테스트 케이스 제한사항
• 입출력 예 #1 문제 예시와 같습니다. • 입출력 예 #2 <초기 맵 상태> 첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다. 두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다. 마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다. 총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.
이 문제는 2차원 배열에서 구간의 변화를 어떻게 효율적으로 처리할지가 관건인 문제입니다. 가장 쉽게 생각할 수 있는 브루트 포스로 풀 경우 정확성 테스트 케이스는 모두 맞출 수 있지만, 시간 복잡도가 O(N * M * K)가 되어 효율성 테스트케이스에서 시간 초과가 발생하게 됩니다. 2차원 배열에 대한 구간의 변화를 처리하는 방법을 설명드리기 전에, 우선 1차원 배열을 효율적으로 처리할 수 있는 방법을 설명드리겠습니다. 예를 들어, O(M)의 시간 복잡도를
O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다. 위의 예시의 경우 이 방식으로 문제를 풀면 O(N * M * K)의 복잡도를 O(N * K)로 줄일 수 있지만, 이 또한 시간 초과가 발생합니다. 따라서 이 아이디어를 2차원 배열로 확장해 줘야 합니다. 이번엔 2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다. 배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면, 1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 됩니다.
위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화와 같습니다. 각 열에 위의 아이디어를 적용시키면 아래와 같습니다. 이런 식으로 2차원 배열에도 적용시킬 수가 있습니다.
즉, 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다. 위 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하거나 왼쪽에서 오른쪽으로 누적합 한 뒤, 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있습니다.
이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다는 것을 알 수 있습니다. 따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다. 그리고 해당 배열을 누적합 배열로 바꾸는 과정이 필요한데, 행과 열을 각각 누적합 해줘야 하기 때문에 O(N * M)가 걸리게 됩니다. 따라서 O(K + N * M)으로 문제를 해결할 수 있습니다. 이해를 돕기 위해 2번 테스트케이스를 예시로 추가 설명드리겠습니다. 1. (1,1)부터 (2,2)까지 -4만큼 변화를 줘야 합니다. (배열의 (1,1)과 (3,3)에 -4, 배열의 (1,3)과 (3,1)에 4만큼 변화를 줍니다.)
2. (0,0)부터 (1,1)까지 -2만큼 변화를 줘야 합니다. (배열의 (0,0)과 (2,2)에 -2, 배열의 (0,2)과 (2,0)에 2만큼 변화를 줍니다.)
3. (2,0)부터 (2,0)까지 +100의 변화를 줘야 합니다. (배열의 (2,0)과 (3,1)에 100, 배열의 (2,1)과 (3,0)에 -100만큼 변화를 줍니다.)
이 배열을 이제 위에서 아래로 누적합 해주겠습니다.
그다음 왼쪽에서 오른쪽으로 누적합 해주겠습니다.
이 배열을
마지막 결과 배열과 같은 배열이 나왔습니다. 이 배열에서 0보다 큰 정수의 개수를 구하면 됩니다. 문제 7 – 사라지는 발판
문제 설명 플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다. 각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1×1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밟음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다. 다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.
게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. ‘이길 수 있는 플레이어’는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, ‘질 수밖에 없는 플레이어’는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다. 아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다. 위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.
위 예시에서 양 플레이어가 최적의 플레이를 했을 경우, 캐릭터의 이동 횟수 합은 5입니다. 최적의 플레이를 하는 방법은 여러 가지일 수 있으나, 이동한 횟수는 모두 5로 같습니다. 게임 보드의 초기 상태를 나타내는 2차원 정수 배열
• 입출력 예 #1 문제 예시와 같습니다. • 입출력 예 #2 주어진 조건을 그림으로 나타내면 아래와 같습니다. 이길 수 있는 플레이어는 B, 질 수밖에 없는 플레이어는 A입니다. 다음은 B가 이기는 방법 중 하나입니다.
위와 같이 플레이할 경우 이동 횟수 6번 만에 게임을 B의 승리로 끝낼 수 있습니다. B가 다음과 같이 플레이할 경우 게임을 더 빨리 끝낼 수 있습니다. 이길 수 있는 플레이어는 최대한 빨리 게임을 끝내려 하기 때문에 위 방법 대신 아래 방법을 선택합니다.
위와 같이 플레이할 경우 이동 횟수 4번 만에 게임을 B의 승리로 끝낼 수 있습니다. 따라서 4를 return 합니다. • 입출력 예 #3 양 플레이어는 매 차례마다 한 가지 선택지밖에 고를 수 없습니다. 그 결과, (0, 2)에서 어디로도 이동할 수 없는 A의 패배합니다. 양 플레이어가 캐릭터를 움직인 횟수의 합은 4입니다. • 입출력 예 #4 게임을 시작하는 플레이어 A가 처음부터 어디로도 이동할 수 없는 상태입니다. 따라서 A의 패배이며, 이동 횟수의 합은 0입니다.
이 문제는 완전 탐색으로 해결할 수 있는 문제입니다. 문제에서 주어진 게임판의 크기가 크지 않고, 발판을 밟으면 사라진다는 조건이 있기 때문에 탐색해야 하는 가짓수가 크게 줄어듭니다. 따라서 완전 탐색을 하더라도 제한 시간 내에 충분히 풀 수 있습니다. 이번에는 재귀 함수를 이용한 완전 탐색으로 해설을 진행하겠습니다. 재귀 함수는 어떤 함수 내에서 자신을 다시 호출하여 작업을 수행하는 함수를 말합니다. 이 문제에서는 게임판의 상태에 따라 이번에 움직여야 하는 플레이어가 이길 수 있는지, 질 수밖에 없는지를 판단하고 판단한 결과와 이동한 횟수를 반환하는 재귀 함수를 구현해서 해결할 수 있습니다. 즉, 함수의 매개변수로 게임판의 상태, A의 위치, B의 위치 등을 넘겨주면, 이번 턴에 움직여야 하는 플레이어의 승패 여부와 총 이동 횟수를 알려주는 함수입니다. 플레이어들의 총 이동 횟수를 이용해 플레이어 A의 턴인지, B의 턴인지 구분하는 방식으로 하나의 재귀 함수로 구현할 수도 있지만, 설명 상의 편의를 위해서 A의 승패 여부와 플레이어의 총 이동 횟수를 반환하는 함수와 B의 승패 여부와 플레이어의 총 이동 횟수를 반환하는 함수를 분리하고, 각각 A 함수와 B 함수라고 부르겠습니다. 이 함수들은 플레이어가 상하좌우 4가지 방향 중 이동할 수 있는 방향으로 이동하여 게임판의 상태를 바꾼 뒤, 그 상태를 상대 플레이어에게 넘기는 방식으로 동작합니다. 즉, A 함수는 플레이어 A를 움직이는 함수, B 함수는 플레이어 B를 움직이는 함수가 되고, A 함수에서는 B 함수를, B 함수에서는 A 함수를 호출하게 됩니다. A 함수와 B 함수는 플레이어의 승패 여부와 이동 횟수를 반환합니다. 따라서 A 함수에서는 B 함수의 호출 결과를 통해 플레이어 B의 승패 여부와 총 이동 횟수를 알 수 있고, B 함수에서는 플레이어 A의 승패 여부와 총 이동 횟수를 알 수 있습니다. 만약 상대 턴으로 넘어간 모든 함수의 결과가 ‘패배’일 경우, ‘나’는 반드시 이길 수 있습니다. 반대로, 상대 턴으로 넘어간 모든 함수의 결과가 ‘승리’일 경우, ‘나’는 무조건 질 수밖에 없습니다. 따라서 함수를 호출한 결과를 종합해 ‘이길 수 있는 방법이 있는지’, ‘질 수밖에 없는지’를 구할 수 있습니다. 그리고 문제에 ‘양 플레이어는 최적의 플레이를 합니다.’라는 조건이 있기 때문에, 승리하는 플레이어는 최소한의 이동으로 승리하고 패배하는 플레이어는 최대한의 이동으로 패배해야 합니다. 따라서 이동 횟수의 최댓값 또는 최솟값을 상대방의 결과에 따라 적절하게 반환해 주면 됩니다. 이러한 방식으로 A 함수와 B 함수를 구현하고, ‘게임은 항상 플레이어 A가 먼저 시작합니다.’라는 문제 조건에 의해 A 함수를 호출해 줍니다. 그러면 A 함수는 함수 내부에서 B 함수를 호출하고, B 함수 역시 함수 내부에서 A 함수를 호출하면서 가능한 모든 경우에 대해서 탐색하게 되고, 결국 초기 매개변수들을 전달한 A 함수의 결과로 최적의 이동 횟수가 반환되는 것을 확인할 수 있습니다.
|