17837 - 새로운 게임 2

정보

• 문제 보기: 17837 - 새로운 게임 2
• 소요 시간: 56분
• 풀이 언어: python
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현

풀이 코드

정보

• 메모리: 32412 KB
• 시간: 44 ms

import sys
input = sys.stdin.readline

n, k = 0, 0
board = []
horse_data = []
horse_board = []
dy = [0, 0, -1, 1] # R L T B
dx = [1, -1, 0, 0]

def move(i):
    global horse_data, horse_board
    
    y, x, d = horse_data[i]
    ny = y + dy[d]
    nx = x + dx[d]
    
    # 1. bound / blue check
    if not (0 <= ny < n and 0 <= nx < n) or board[ny][nx] == 2:
        # change direction
        d = d-1 if d & 1 else d+1
        horse_data[i][2] = d
        
        # recheck
        ny = y + dy[d]
        nx = x + dx[d]
        if not (0 <= ny < n and 0 <= nx < n) or board[ny][nx] == 2:
            return False
            
    # get idx of target horse from horse stack
    idx = horse_board[y][x].index(i)
    movable = horse_board[y][x][idx:]
    horse_board[y][x] = horse_board[y][x][:idx]
    
    # 2. white check
    if board[ny][nx] == 0:
        horse_board[ny][nx].extend(movable)
    # 3. red check
    elif board[ny][nx] == 1:
        horse_board[ny][nx].extend(movable[::-1])
        
    # update moved horse data
    for hdx in movable:
        horse_data[hdx][0] = ny
        horse_data[hdx][1] = nx
        
    # end if stacked size gte 4
    if len(horse_board[ny][nx]) >= 4:
        return True
    
    return False

def solution():
    global n, k, board, horse_data, horse_board
    
    n, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    horse_board = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(k):
        y, x, d = map(int, input().split())
        horse_board[y-1][x-1].append(i)
        horse_data.append([y-1, x-1, d-1])
        
    # simulate
    for turn in range(1, 1001):
        for i in range(k):
            if move(i):
                print(turn)
                return
        
    print(-1)
    
    
if __name__ == '__main__':
    solution()

풀이 해설

파이썬 리스트 슬라이싱은 무적이고 신이다.

horse_data에는 tuple이 아닌 list 형식으로 데이터를 저장하는 것이 좋다.

로직 상 말의 방향(3번째 원소)을 수정할 일이 있기 때문이다.

메모

• 빡구현 문제 치고 그렇게 머리터지지 않았음. (이 문제 바로 전에 게리맨더링 2를 풀어서 그 영향일수도 ㅎ)
• 빡구현 풀이 시간이 늘어지는 편이므로 연습이 더 필요해보임.