[Python] 16883번 대각 게임 / 26102번 Card Game

https://www.acmicpc.net/problem/16883

https://www.acmicpc.net/problem/26102

---

 

25/08/27

 

 

제한만 20과 25로만 약간 다르고, 입력 문자열과 출력 문자열이 약간 다른 것 빼고는 완전히 같은 문제이다.

---

 

문제 접근 방식:

 

 

이전에 Wall Making Game을 풀었던 사람이라면 쉽게 해결할 수 있는 문제이다.

 

방식은 거의 동일하나 이번에는 대각선으로 판이 분할이 되며, 항상 4개의 판으로 쪼개지지 않는다는 점이 조금 다르다.

 

추가로, 보드판을 체스판처럼 생각한다면 검은 색 칸과 흰색칸은 서로가 서로에게 영향을 주지 못하므로, 흰색 칸만 모은 판과 검은색 칸만 모은 판으로 한 보드를 독립적인 두 개의 보드로 분리해서 생각할 수 있다.

 

판을 45도 돌리는 방법으로 비숍 문제를 해결한 사람이라면, 이후의 과정은 쉽게 해결할 수 있을 것이다.

 

흑/백 분리 후 45도를 회전 시킨다.

 

이후에는 Wall Making Game을 진행하면 되는데, 다음과 같은 DP를 정의하자.

 

$$DP[u][d][l][r] = [u, d] \times [l, r]크기의 \ subboard의 \ 그런디 수$$

 

해당 DP를 야무지게 채워주면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16883번 대각 게임
# 구현, 스프라그-그런디 정리, 다이나믹 프로그래밍
'''
접근 방법:
26102번과 동일
'''
import sys
input = sys.stdin.readline

# [-] mex함수 정의
def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)

# [-] 입력부
N, M = map(int, input().split())

# [-] 원본 배열 입력받기 + 패딩
MAP = [[0 for _ in range(25)] for _ in range(25)]
for i in range(N):
    row = input().rstrip()
    for j in range(M):
        MAP[i][j] = row[j]

# [-] 해당 원본 배열을 흑/백 분리 및 45도 회전
game1, game2 = [[0 for _ in range(25)] for _ in range(25)], [[0 for _ in range(25)] for _ in range(25)]
for s in range(49):
    # [-] 새로운 배열의 row는 s//2다.
    new_row = s//2
    # [-] 변환
    for col in range(s+1):
        row = s-col
        if row < 0 or row >= 25: continue
        if col < 0 or col >= 25: continue
        if s % 2 == 0:
            game1[new_row][12-new_row+col] = MAP[row][col]
        else:
            game2[new_row][12-new_row+col] = MAP[row][col]

# [-] 각각의 배열 차원 축소
minr, minc, maxr, maxc = 26, 26, -1, -1
for r in range(25):
    for c in range(25):
        if game1[r][c] != 0:
            minr, maxr = min(minr, r), max(maxr, r)
            minc, maxc = min(minc, c), max(maxc, c)
game1 = [row[minc:maxc+1] for row in game1[minr:maxr+1]]
minr, minc, maxr, maxc = 26, 26, -1, -1
for r in range(25):
    for c in range(25):
        if game2[r][c] != 0:
            minr, maxr = min(minr, r), max(maxr, r)
            minc, maxc = min(minc, c), max(maxc, c)
game2 = [row[minc:maxc+1] for row in game2[minr:maxr+1]]

# [-] game1에 대한 계산
R = len(game1)
try:
    C = len(game1[0])
except IndexError:
    C = 0
# [-] 정의 : DP[r1][r2][c1][c2] = [r1, r2]x[c1, c2]부분 배열의 그런디 수
DP1 = [[[[-1 for _ in range(C)]
         for _ in range(C)]
         for _ in range(R)]
         for _ in range(R)]
# [-] 배열 초기화
for r1 in range(R):
    for r2 in range(r1):
        for c1 in range(C):
            for c2 in range(C):
                DP1[r1][r2][c1][c2] = 0
for r1 in range(R):
    for r2 in range(R):
        for c1 in range(C):
            for c2 in range(c1):
                DP1[r1][r2][c1][c2] = 0

# [-] 우리는 DP1[0][R-1][0][C-1]을 구하고 싶다.
def dfs1(r1, r2, c1, c2):
    # [-] 말도 안되는 경우
    if r1 > r2 or c1 > c2:
        return 0
    # [-] 이미 존재하는 경우
    if DP1[r1][r2][c1][c2] != -1:
        return DP1[r1][r2][c1][c2]
    # [-] 존재하지 않지만 같은 경우
    if r1 == r2 and c1 == c2:
        if game1[r1][c1] == 0:
            DP1[r1][r2][c1][c2] = 0
        else:
            DP1[r1][r2][c1][c2] = 1
        return DP1[r1][r2][c1][c2]
    # [-] 존재하지도 않고 같지도 않은 경우
    ret = set()
    for r in range(r1, r2+1):
        for c in range(c1, c2+1):
            if game1[r][c] == 0:
                continue
            if game1[r][c] == 'L':
                ret.add(dfs1(r1, r-1, c1, c2) ^ dfs1(r+1, r2, c1, c2))
            elif game1[r][c] == 'R':
                ret.add(dfs1(r1, r2, c1, c-1) ^ dfs1(r1, r2, c+1, c2))
            else:
                ret.add(dfs1(r1, r-1, c1, c-1) ^ dfs1(r+1, r2, c1, c-1) ^ dfs1(r1, r-1, c+1, c2) ^ dfs1(r+1, r2, c+1, c2))
    DP1[r1][r2][c1][c2] = mex(ret)
    return DP1[r1][r2][c1][c2]
game1_grundy = dfs1(0, R-1, 0, C-1)

# [-] game2에 대한 계산
R = len(game2)
try:
    C = len(game2[0])
except IndexError:
    C = 0
# [-] 정의 : DP[r1][r2][c1][c2] = [r1, r2]x[c1, c2]부분 배열의 그런디 수
DP2 = [[[[-1 for _ in range(C)]
         for _ in range(C)]
         for _ in range(R)]
         for _ in range(R)]
# [-] 배열 초기화
for r1 in range(R):
    for r2 in range(r1):
        for c1 in range(C):
            for c2 in range(C):
                DP2[r1][r2][c1][c2] = 0
for r1 in range(R):
    for r2 in range(R):
        for c1 in range(C):
            for c2 in range(c1):
                DP2[r1][r2][c1][c2] = 0

# [-] 우리는 DP2[0][R-1][0][C-1]을 구하고 싶다.
def dfs2(r1, r2, c1, c2):
    # [-] 말도 안되는 경우
    if r1 > r2 or c1 > c2:
        return 0
    # [-] 이미 존재하는 경우
    if DP2[r1][r2][c1][c2] != -1:
        return DP2[r1][r2][c1][c2]
    # [-] 존재하지 않지만 같은 경우
    if r1 == r2 and c1 == c2:
        if game2[r1][c1] == 0:
            DP2[r1][r2][c1][c2] = 0
        else:
            DP2[r1][r2][c1][c2] = 1
        return DP2[r1][r2][c1][c2]
    # [-] 존재하지도 않고 같지도 않은 경우
    ret = set()
    for r in range(r1, r2+1):
        for c in range(c1, c2+1):
            if game2[r][c] == 0:
                continue
            if game2[r][c] == 'L':
                ret.add(dfs2(r1, r-1, c1, c2) ^ dfs2(r+1, r2, c1, c2))
            elif game2[r][c] == 'R':
                ret.add(dfs2(r1, r2, c1, c-1) ^ dfs2(r1, r2, c+1, c2))
            else:
                ret.add(dfs2(r1, r-1, c1, c-1) ^ dfs2(r+1, r2, c1, c-1) ^ dfs2(r1, r-1, c+1, c2) ^ dfs2(r+1, r2, c+1, c2))
    DP2[r1][r2][c1][c2] = mex(ret)
    return DP2[r1][r2][c1][c2]
game2_grundy = dfs2(0, R-1, 0, C-1)

# [-] 정답 출력
ans = game1_grundy^game2_grundy
if ans > 0:
    print('koosaga')
else:
    print('cubelover')