[2022 KAKAO Blind Recruitment] Q7. 사라지는 발판 (C++, Python, Java)

문제 링크

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)

  Comments
  • 킹갓독
    킹갓독님은 정말 못하시는 게 없으십니다 ㄷㄷ 카카오 코테 가볍게 올솔 ㄷㄷ
  • zero2vec
    인공지능까지 섭렵한 킹갓독..
  • 안녕하세요 포스팅 잘 보고 있습니다. 코드 정말 깔끔하게 짜시는 것 같아요.
    코드와 알고리즘에서 하나 이해가 안가는 부분이 있는데요,

    일단 제가 보고 이해한 바로는 A, B 둘 다 자신이 이긴 경우를 바탕으로 비교를 진행합니다.
    한번이라도 이기면 다른 지는 경우에 대해서는 고려하지 않습니다.

    근데 예를 들어, B가 실수하지 않는다면 B가 이기는 게임에서 B가 실수해서 A가 이기는 한 가지 경우가 있다고 했을 때 결국 함수의 반환값은 A가 이기는 하나의 경우에 대해서 반환한다고 이해했습니다.

    혹시 해당 경우가 어떻게 걸러지게 되는지 간단하게라도 설명 부탁드려도 될까요?

    A와 B가 누가 이기는지 어떻게 판단할 수 있는지 이해가 잘 가지 않습니다.
    • "해당 경우가 어떻게 걸러지게 되는지 간단하게라도 설명 부탁드려도 될까요?" 라는 질문을 이해를 못하겠어요ㅠ

      그냥 풀이에 대해 다시 풀어서 써보면, solve 함수는 현재 상황에서 두 캐릭터가 최선으로 플레이했을 때 두 캐릭터가 움직인 횟수의 총합을 의미해요. 저 함수가 왜 그렇게 되는건지 이유를 모르겠다 싶을 수 있지만 그건 그냥 재귀적으로 받아들여야 해요.

      그러면 현재 플레이어가 상/하/좌/우로 움직인 후 solve를 호출한 값에서 1을 더하면 현재 플레이어가 상/하/좌/우로 움직였을 때 두 캐릭터가 움직인 횟수의 총합을 의미하고

      이 값이 짝수이면 플레이어의 패배, 홀수이면 플레이어의 승리여서 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우, 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우, 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우라고 써놓은 것과 같이 계산이 가능해요.
    • 답변 감사합니다. 뭔가 아리송하지만 알것도 같아요..
      제 질문은 코드상에서 '최선'의 플레이가 어떻게 보장되는지? 였습니다.
      minimax tree에 대해 좀 더 찾아보고 이해해보도록 하겠습니다.
      다시한번 감사드립니다!
  • THANKS
    안녕하세요, 바킹독님.

    좋은 포스팅 올려주셔서 덕분에 조금이나마 가닥을 잡을 수 있었습니다.
    알고리즘의 기본적인 흐름은 머리에서 정리가 된 것 같으나 한 가지 잘 이해가 되지 않는 점이 있어 질문드립니다...!

    반환 값이 짝수일 때 플레이어가 패배하고, 홀수일 때 승리한다고 하셨는데 해당 조건이 어떻게 도출되었는지 잘 모르겠습니다.

    4가지의 예시 케이스를 분석했을 때 귀납적으로 조건을 도출하신 건지, 혹은 문제 설명에서 어떠한 힌트를 얻으신 건지 알려주시면 정말 감사드리겠습니다!
  • 권현성
    # 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우
    if ret % 2 == 0 and val % 2 == 1:
    ret = val # 바로 갱신
    # 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우
    elif ret % 2 == 0 and val % 2 == 0:
    ret = max(ret, val) # 최대한 늦게 지는걸 선택
    # 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우
    elif ret % 2 == 1 and val % 2 == 1:
    ret = min(ret, val) # 최대한 빨리 이기는걸 선택

    이 코드 부분 추가 설명 가능한가요?
    ret와 val 의 정확한 쓰임새를 모르겠습니다.
    • solve 함수는 현재 상태에서 둘 다 최적의 플레이를 할 때 남은 이동 횟수를 반환합니다.

      ret은 해당 함수에서 반환할 값이고 val은 플레이어가 4개의 각 방향으로 이동했을 때 남은 이동 횟수입니다. (그렇기 때문에 val = solve(opx, opy, nx, ny)+1으로 계산됨)

      "현재 저장된 턴" = ret이고 "새로 계산된 턴" = val입니다. 나머지 디테일은 코드의 주석과 이 글에 달려있는 다른 댓글들 참고해서 이해해보세요.
  • hiwg08
    덕분에 이해가 쏙쏙 됐습니다.... 너무 감사드려요
댓글 쓰기