[파이썬] 28218 격자 게임 (백준, KOI 1차)

1. 문제 설명

문제 : 28218 - 격자 게임 https://www.acmicpc.net/problem/28218

사용 언어 : 파이썬 (Pypy3)

 

문제요약 :

NM의 보드에서 말이 아래로 한 칸, 오른쪽으로 한 칸, 오른쪽 아래 대각선 방향으로 1~K칸 움직일 수 있다.

두 명의 사람이 돌아가면서 말을 NM의 위치로 옮긴다고 할 때, 말의 시작 위치에 따라 누가 NM칸으로 옮길 수 있는지 구하시오.

---

2. 문제 풀이

해설 :

 

N, M, K가 다 300 이하이기 때문에 300^3으로 쉽게 구할 수 있습니다.

 

거꾸로 보며 갈 수 있는 곳에 Lose (무조건 질 수밖에 없는 칸)가 하나라도 주어진다면 Win (무조건 이길 수밖에 없는 칸)으로 표시합니다. 갈 수 있는 곳이 모두 Win이라면 Lose로 표시합니다.

 

게임이론을 알고 있으면 쉽게 풀 수 있는 문제입니다. 저는 코드 작성의 편한함을 위해 보드를 돌려서 진행하였습니다.

 

코드 :

import sys; input = sys.stdin.readline

N, M, K = map(int,input().split())
board = [list(input().rstrip())[::-1] for i in range(N)][::-1]
dp = [[False for i in range(M)] for j in range(N)]

for i in range(N):
    for j in range(M):
        if i != 0 and board[i-1][j] == '.': dp[i][j] |= not dp[i-1][j]
        if j != 0 and board[i][j-1] == '.': dp[i][j] |= not dp[i][j-1]

        for k in range(1, K+1):
            if i-k >= 0 and j-k >= 0:
                if board[i-k][j-k] == '.':
                    dp[i][j] |= not dp[i-k][j-k]
            else: break

result = []
for i in range(N):
    result.append(dp[i][::-1])
result.reverse()

ans = []
Q = int(input())
for i in range(Q):
    x, y = map(int,input().split())
    ans.append('First' if result[x-1][y-1] else 'Second')

print('\n'.join(ans))

---

3. 추가로...

이 문제 시험장에서 풀었던 사람으로써 이걸 왜 못 풀었나 하염없이 눈물만...ㅠㅠ

---

앞으로 코딩과 알고리즘 관련 글을 업로드할 예정입니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!