백준: 17837 새로운 게임 2

문제

17837번: 새로운 게임 2

 

문제 풀이

 문제의 요구상을 그대로 구현하면 된다. 비슷한 시뮬레이션 문제로는 어른 상어이지 않을까 싶다. 이전에 다룬 문제보다 까다로운 것은 체스 말이 중첩되는 경우, 그대로 쌓인다는 것이다. 또한 이동할 때 현재 체스 말의 번호와 쌓인 체스 말들을 판단하여서 이동시켜야 한다는 것이 달랐다. 여기에 초기에 주어지는 정보에 흰색, 빨간색, 파란색의 색깔이 구분되는 칸이 주어지면 각 칸들에 따라 다르게 동작하여야 한다.

 

• 흰색인 경우 그대로 이동한다.
• 빨간색인 경우 이동하려는 말을 뒤집어서 이동한다.
  • 예를 들어 이동하려는 칸에 A, B, C가 있다면 C, B, A 가 된다.
• 파란색과 범위를 벗어나는 경우에는 방향을 반대로 바꾼다.
  • 방향을 반대로 바꾼 후에도 동일한 상황이 발생(파란색 or 범위를 벗어남)한다면, 가만히 있는다.

 위의 상황들을 잘 고려하여서 그대로 코드로 작성하면 된다. 문제를 풀면서 잘 못 생각했던 부분은 중첩된 경우 한 번에 이동시키면 된다고 생각하였다. (사실, 그림 예제를 자세히 안 보고 문제를 풀었다.😥) 생각한 데로 작성했는데 틀렸습니다가 계속 나와서 찾아보니 현재 이동하려는 말 번호보다 위에 있는 것은 같이 움직이고, 아래에 있는 것은 그대로 두어야 한다는 것을 알았다. 이 역시 그대로 작성하면 문제의 정답을 찾을 수 있다.

 

코드

from sys import stdin

RED, BLUE = 1, 2


def visitable(r, c):
    return 0 <= r < N and 0 <= c < N


def move_cp(cp_idx):
    r, c, cur_dir = cp_loc[cp_idx]
    dr, dc = dirs[cur_dir]
    next_r, next_c = r + dr, c + dc

    if not visitable(next_r, next_c) or board[next_r][next_c] == BLUE:
        dr, dc = dirs[reversed_dir[cur_dir]]
        next_r, next_c = r + dr, c + dc
        # 방향만 반대로 변경
        cp_loc[cp_idx][2] = reversed_dir[cur_dir]

        if not visitable(next_r, next_c) or board[next_r][next_c] == BLUE:
            return False

    # 겹쳐지는 경우를 생각하여, 위 아래 말들을 판별하여야 함
    idx = check[r][c].index(cp_idx)
    temp = check[r][c][idx:]
    check[r][c] = check[r][c][:idx]

    # 빨간색인 경우 뒤집음
    if board[next_r][next_c] == RED:
        temp = temp[::-1]

    # 위치 정보를 하나씩 변경
    for cp_idx in temp:
        check[next_r][next_c].append(cp_idx)
        cp_loc[cp_idx][:2] = [next_r, next_c]

    return len(check[next_r][next_c]) >= 4


if __name__ == '__main__':
    # 우, 좌, 상, 하
    dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))
    reversed_dir = {0: 1, 1: 0, 2: 3, 3: 2}

    N, K = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]
    check = [[[] for _ in range(N)] for _ in range(N)]

    # chase piece location
    cp_loc = [list(map(int, stdin.readline().split())) for _ in range(K)]

    # 인덱스에 맞게 1씩 감소
    for idx, cp in enumerate(cp_loc):
        x, y, cur_dir = cp
        cp_loc[idx] = [x - 1, y - 1, cur_dir - 1]
        check[x - 1][y - 1].append(idx)

    time = 1
    while time <= 1000:
        for i in range(K):
            if move_cp(i):
                print(time)
                exit(0)
        time += 1
    print(-1)