17837 - 새로운 게임 2

 

---

 

문제

https://www.acmicpc.net/source/62767025

로그인

 

풀이

해당 문제는 자기 위에 올라가있는 친구들을 어떻게 잘 관리하는지가 핵심인데, 덱을 사용하면 손쉽게 관리할 수 있다.

 

예로 다음칸이 흰색이고 순서가 3일 경우를 보자. (배열 왼쪽이 낮은 위치)

[2, 3, 1, 4] , [5, 6] 이라고 할 경우 [5, 6, 3, 1, 4] 가 되어야한다.

 

이 과정은 덱을 활용해서 [2, 3, 1, 4] 에서 뒤에서부터 4, 1, 3 을 순서대로 pop하고, 임시 덱에 pop한 값을 왼쪽부터 넣으며 

[3, 1, 4] 로 만들 수 있다.

 

빨간 칸은 더 쉽다. 

[2, 3, 1, 4], [5, 6] => [5, 6, 4, 1, 3] 를 만들어야하는데 중간에 임시 덱을 둘 필요도 없이 pop 및 append를 바로 해주면 된다.

 

파란칸이나 범위가 벗어났을때에는 우선 방향을 바꿔준다.

그리고 반대로 가야하는 곳도 파란색이나 범위가 벗어나면 그냥 pass하면 된다.

만약 흰색칸이나 빨간색칸이면 위의 로직을 그대로 실행하면 된다.

 

핵심요소는 이렇고, 전반적인 풀이는

1 ~ k까지 순서가 돌아가는데 딕셔너리로 key는 순서, value는 좌표를 저장한다. 해당 좌표로 해당 순서가 어느 덱에 들어있는지 바로 찾을 수 있다. (물론 핵심요소가 실행될 때 좌표도 갱신해줘야 한다.)

 

코드

from sys import stdin
from collections import deque
'''

이동시, 자기 위의 친구들과 함께 어떻게 잘 이동할것인지를 생각해야함.

'''

def whiteProcess(x, y, nx, ny, seq):
    global colors, board, position
    tempDeque = deque()
    while board[x][y]:
        val = board[x][y].pop()
        tempDeque.appendleft(val)
        position[val] = (nx, ny, position[val][2])
        if val == seq: break
    while tempDeque:
        board[nx][ny].append(tempDeque.popleft())

    return len(board[nx][ny])

def redProcess(x, y, nx, ny, seq):

    global colors, board, position

    while board[x][y]:
        val = board[x][y].pop()
        board[nx][ny].append(val)
        position[val] = (nx, ny, position[val][2])
        if val == seq: break

    return len(board[nx][ny])

def changeDir(d):
    if d == 0 : return 1
    if d == 1 : return 0
    if d == 2 : return 3
    if d == 3 : return 2

# →, ←, ↑, ↓
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

n, k = map(int, input().split())

colors = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
position = {}
board = [ [deque() for _ in range(n)] for _ in range(n) ]

for num in range(1, k + 1):
    x, y, d = map(int, stdin.readline().rstrip().split())
    board[x-1][y-1].append(num)
    position[num] = (x-1, y-1, d-1)

seq = 1
turn = 1
while True:
    if seq > k:
        turn += 1
        seq = 1

    if turn > 1000:
        break

    x, y, d = position[seq]
    # 이동할려는 위치
    nx = x + dx[d]
    ny = y + dy[d]

    totalSize = 0

    # 범위 벗어나거나, 값이 2라면
    if nx < 0 or nx >= n or ny < 0 or ny >= n or colors[nx][ny] == 2:
        # 방향을 변경시켜준다.
        position[seq] = (x, y, changeDir(d))
        # 목적 위치를 새로 갱신한다.
        tx = x - dx[d]
        ty = y - dy[d]

        # 새로운 목적지도 범위가 벗어나거나, 파란색이라면 방향만 바꿔주고 그냥 둔다.
        if tx < 0 or tx >= n or ty < 0 or ty >= n or colors[tx][ty] == 2:
            pass
        # 둘 다 아니라면 빨강이나 흰색을 판단하고 같은 로직을 실행해준다.
        else:
            if colors[tx][ty] == 0:
                totalSize = whiteProcess(x, y, tx, ty, seq)
            elif colors[tx][ty] == 1:
                totalSize = redProcess(x, y, tx, ty, seq)

    # 범위내에 있으며, 파란색이 아닐 경우에
    else:
        if colors[nx][ny] == 0:
            totalSize = whiteProcess(x, y, nx, ny, seq)
        elif colors[nx][ny] == 1:
            totalSize = redProcess(x, y, nx, ny, seq)

    if totalSize >= 4:
        break

    # for b in board:
    #     print(b)
    # print()

    seq += 1

print(turn) if turn <= 1000 else print(-1)

 

후기

자잘한 실수가 계속된다. 좌표는 1,1 부터, 방향값도 1~4였는데 이런거 체크 제대로 못해서 시간 날리고..

지문 꼼꼼히 읽는거 ..ㅠㅠ 신경쓰자