Python/백준] 17837 새로운 게임 2

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

내가 해봤던 보드게임이랑 매우 비슷한 문제여서 설계단계가 쉬웠다.

<문제 해설>

구현 문제이다. 자료구조 선택이 중요한거 같다. 

시간을 매우 짧게 줬고 공간을 매우 넓게 주었음으로 공간을 최대한 활용해서 시간을 줄이는 것이 키포인트 이다.

나는 2차원 stack 공간 pieceOnBoard  + 2차원 색을 저장할 체스판  board + 각각의 체스말의 위치 저장 리스트 pieces를 사용해서 풀었다.

처음에는 빨간색 칸으로 이동할때 stack를 사용해서 현재 체스말 위치칸에서 pop하고 다음에 위치하게 될 체스말 위치칸으로 append하는 식으로해서 반대로 돌리고

흰색으로 갔을땐 que를 사용해서 앞에서 부터 뺄까 생각했는데 이동하지 않는 말이 앞에 위치할 수 있어서 그리고 한칸에 많아봤자 3개의 stack만 지우면 되서 그냥 stack(리스트)을 사용한다.

 

• 각칸에 stack을 가지고 있는 2차원 판을 생성한다.
• 만약 한칸이라도 4개의 말 이상이면 게임 종료
• 각각의 체스말을 저장하는 리스트를 만들어 [y좌표, x좌표, 방향] 으로 저장 리스트의 첫칸은 1번말 이런식
• 게임 1 총이동당 체스말 리스트를 for문으로 처음부터 훑으면 1번 말부터 이동시키는 것과 같은 효과
• 움직일 곳이 어딘지에 따라 다르게 이동함

1. 일단 y좌표랑 x좌표를 v을 통해서 이동시킨 my,. mx를 얻음
2. my mx가 board의 안에 없거나 2차원 색을 저장할 체스판이 파란색으로 이동한다면
   v값을 반대로 바꿔주고 my, mx를 변경된 v값으로 다시계산 변경된 v는 pieces배열에도 적용시킨다.
3. 만약 board의 밖으로 나가거나 체스판이 파란색으로 이동하면 더이상 움직이지 않는다고 했으니 정지
   (파란색을 만나서 반대로 이동할때 반대쪽이 흰색이면 아래 5번으로 간다. 빨강이면 6번)
4. 3번이 참이 아닐경우 움직여야함 이제 흰색으로 움직이는지 빨간색으로 움직이는지 봐야함
5. 흰색인경우
   pieceOnBoard에서 내가 지금 움직일 말의 스텍에서의 좌표를 찾고 (이건 앞에서 미리 찾아두는데 설명을 위해서 지금하는 것처럼 설명 어떤색이든 찾아야 함으로) 스택의 좌표부터 끝까지를 빼서 다음이동할 좌표로 이동시킨다. 그리고 이동시킨 말들의 위치를 pieces에서 좌표수정
6. 빨간색인 경우
   똑같이 스택에서 움직일 말의 좌표를 찾고 pop해서 움직일 좌표에 append해준다. 이는 꺼꾸로 들어가는 모습을 보여줄 수 있다. 그리고 흰색이랑 똑같이 이동시킨 말들의 위치를 pieces에서 좌표수정

• 이렇게 반복하다가 한곳이라도 4개 이상의 말이 모인다면 정지시키고 answer변수에 저장했던 게임 라운드가 몇번 진행됐는지 출력
• 라운드가 1000번이 넘어도 출력

<코드>

import sys

N, K = map(int, sys.stdin.readline().split())

board = []
pieceOnBoard = []
pieces = []

for n in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))
    pieceOnBoard.append([[] for i in range(N)])

for k in range(K):
    y, x, v = map(int, sys.stdin.readline().split())
    pieceOnBoard[y - 1][x - 1].append(k + 1)
    pieces.append([y - 1, x - 1, v - 1])

answer = -1
move = [(0,1),(0,-1),(-1,0),(1,0)]
def changV(v):
    if v == 0:
        return 1
    elif v == 1:
        return 0
    elif v == 2:
        return 3
    else:
        return 2


# 0흰색, 1 빨간색, 2 파란색
flag = 0
while(1):
    answer += 1
    if flag == 1:
        print(answer)
        break
    elif answer > 1000:
        print(-1)
        break

    for k in range(K):
        y, x, v = pieces[k]
        number = k + 1

        my = y + move[v][0]
        mx = x + move[v][1]
        index = pieceOnBoard[y][x].index(number)
        if 0 > my or my >= N or 0 > mx or mx >= N or board[my][mx] == 2:
            v = changV(v)
            my = y + move[v][0]
            mx = x + move[v][1]
            pieces[k][2] = v

        if 0 <= my < N and 0 <= mx < N and board[my][mx] != 2:
            if board[my][mx] == 0:
                pieceOnBoard[my][mx] += pieceOnBoard[y][x][index:]
                for _ in range(len(pieceOnBoard[y][x]) - index):
                    popedPiece = pieceOnBoard[y][x].pop()
                    pieces[popedPiece - 1][0] = my
                    pieces[popedPiece - 1][1] = mx

            elif board[my][mx] == 1:
                for _ in range(len(pieceOnBoard[y][x]) - index):
                    popedPiece = pieceOnBoard[y][x].pop()
                    pieceOnBoard[my][mx].append(popedPiece)
                    pieces[popedPiece - 1][0] = my
                    pieces[popedPiece - 1][1] = mx

            if len(pieceOnBoard[my][mx]) >= 4:
                flag = 1
                break

 

<고찰>

오랜만에 문제를 포스팅 했는데, 이유는 그냥 오랜만에 적고 싶었다. 하던 프로젝트가 잠시 못하게 된것이 크다 ㅠㅠ 그리고 보드게임 하고싶다.