[백준 17837] 새로운 게임 2 - Python

Algorithm

시뮬레이션

Logic

zoneInfo: 칸의 정보를 담음

-> Map의 크기를 (N+2) * (N+2) 로 늘려서 바깥 부분은 파란색 구역으로 만든다.

chessMap: 체스 list를 원소로 갖는 2차원 Map

(한 구역에 체스말이 여러개인 경우, 밑에 위치하는 체스 index가 더 작음- stack 구조)

chessInfo: 체스말의 좌표를 저장하는 리스트 -> 이 리스트를 사용하면 2차원 순회할 필요가 없어진다

moveChess(): 체스 번호를 순회하면서 해당 번호의 체스를 움직이는 함수

체스 번호가 위치한 Map에서 그 번호를 만날 때까지 원소들 pop해서 newList의 앞부분에 insert한다.

updateMap(now_y, now_x, False, newList, target_dir)

• target_dir로 new_y, new_x를 구한다.

• 새 좌표가 어느 구역에 속하는 지 확인

  • 흰색 구역

    새 좌표에 newList의 원소들을 추가하고, chessInfo를 갱신한다.

  • 빨간색 구역

    새 좌표에 newList의 원소들을 반대로 추가하고, chessInfo를 갱신한다.

  • 파란색 구역

    처음 방문인 경우: 방향을 반대로 바꿔서 updateMap 함수 다시 호출

    두번째 방문인 경우: 기존의 위치(now_y, now_x)에 newList 추가한다. -> 원래 모습으로 돌려놓는 작업

Review

걸린 시간: 1시간 45분

파란색 구역일 때의 작업을 처음에 잘못해서 디버깅하면서 찾느라고 좀 걸렸다,,

오늘 처음으로 파이참을 써서 디버깅 단축키도 잘 몰라서 더 오래걸린것 같다

익숙해지도록 하자 !!

두 달전에 실패했던 건데 한방에 풀어서 기분이 좋당

Code

N, K = map(int, input().split())
zoneInfo = [[2 for _ in range(N+2)] for _ in range(N+2)]
chessMap = [[[] for _ in range(N+2)] for _ in range(N+2)]
pos = [[0,1],[0,-1],[-1,0],[1,0]]
change = [1,-1,1,-1]
endFlag = False
endTurn = 0

def isEndCondition(y, x):
    if len(chessMap[y][x]) >= 4:
        return True
    return False

def updateMap(now_y, now_x, blue_flag, newList, target_dir):
    global endFlag

    new_y = now_y + pos[target_dir - 1][0]
    new_x = now_x + pos[target_dir - 1][1]

    if zoneInfo[new_y][new_x] == 0:  # white zone
        # update chessInfo, chessMap
        for nl in newList:
            chessInfo[nl[0]] = [new_y, new_x]
            chessMap[new_y][new_x].append(nl)
        if isEndCondition(new_y, new_x):
            endFlag = True
    elif zoneInfo[new_y][new_x] == 1:  # red zone
        newList.reverse()
        for nl in newList:
            chessInfo[nl[0]] = [new_y, new_x]
            chessMap[new_y][new_x].append(nl)
        if isEndCondition(new_y, new_x):
            endFlag = True
    elif zoneInfo[new_y][new_x] == 2:  # blue zone
        if blue_flag:
            for nl in newList:
                chessMap[now_y][now_x].append(nl)

        if not blue_flag:
            blue_flag = True
            target_dir += change[target_dir - 1]
            newList[0][1] = target_dir
            updateMap(now_y, now_x, blue_flag, newList, target_dir)

def moveChess():
    global endFlag
    for i in range(K): # 체스 번호 하나씩 옮김
        now_y = chessInfo[i][0]
        now_x = chessInfo[i][1]

        newList = []
        while True:
            chess = chessMap[now_y][now_x].pop()
            newList.insert(0, chess)
            if chess[0] == i:
                target_dir = chess[1]
                break

        updateMap(now_y, now_x, False, newList, target_dir)

        if endFlag:
            break

for i in range(1, N+1):
    Input = [int(x) for x in input().split()]
    for j in range(1, N+1):
        zoneInfo[i][j] = Input[j-1]

chessInfo = []
for i in range(K):
    chessInfo.append([int(x) for x in input().split()])

for i in range(K):
    y = chessInfo[i][0]
    x = chessInfo[i][1]
    Dir = chessInfo[i][2]

    chessMap[y][x].append([i, Dir])

for i in range(1001):
    moveChess()
    if endFlag:
        endTurn = i+1
        break

if not endFlag:
    endTurn = -1

print(endTurn)