17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하�
www.acmicpc.net
색깔을 저장할 color 배열
체스판 위의 말들을 표시할 board
말들의 상태를 관리할 horse
보통 이런 문제를 풀 때는 board판 위에 움직여야 할 아이템들의 정보를 저장하고 board를 탐색하곤 했는데,
이번에는 보드판 따로, 아이템들의 정보 따로 저장했다.
그 이유는 0번부터 K-1번의 말이 움직일 때 그 이전의 말이 움직임이 그 다음 말에 영향을 주도록 해야 하기 때문이다.
예를 들어 낚시왕 같은 문제의 경우 이전 상어가 움직였을 때의 결과를 다른 곳에 따로 저장해야 했다. 한 사이클 동안 모든 상어가 동시에 움직인다고 했기 때문이다.
하지만 이번 문제는 말들이 순서대로 움직인다고 했기 때문에 board를 그대로 사용하고,
한 턴마다 0~K-1번의 말들을 움직이기 위해서 horse 리스트에 따로 말들의 정보를 저장했다.
일단 주의해야 할 점은 파란색이거나 벽으로 막혀서 후진해야 될 때도 그 후진하려는 곳이 빨간색인지 흰색인지 구분하고 그대로 실행해줘야 한다는 것이다.
그리고 양쪽다 파란색이거나 벽으로 막혀서 움직이지 않을 때도 일단 방향은 바꿔주어야 한다.
그렇게 한번 움직임이 막힌 말은 더이상 움직이지 않을거라고 생각했는데,
말이 움직일 때 '그 위에 있는 말들'이 같이 움직이는 경우가 있으므로 왼오로 움직이던 말이 아래쪽 말에 영향을 받아서 상하로 움직일 수가 있다. 사면초가를 벗어날 수 있다는 뜻이다.
import sys
def solve():
four = False
for t in range(1001):
for num_horse in range(K): # 0~K-1번의 말을 순서대로 이동시키는 것이 한 '턴'
r, c, direct = horse[num_horse]
next_r = r + dx[direct]
next_c = c + dy[direct]
idx = board[r][c].index(num_horse) # 체스판에서의 말의 인덱스
if 0 <= next_r < N and 0 <= next_c < N:
if color[next_r][next_c] == WHITE: # h 위에 있는 모든 말이 이동하고 그 위에 쌓는다
board[next_r][next_c].extend(board[r][c][idx:]) # 이동하려는 말+그 위에 있는 말들을 이동시킨다
for _ in range(idx, len(board[r][c])): # 말들의 정보 horse 리스트를 업데이트하고, 원래 있던 위치에서 삭제
horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
del board[r][c][-1]
if len(board[next_r][next_c]) >= 4:
four = True
break
elif color[next_r][next_c] == RED: # h 위에 있는 말의 순서를 모두 바꾼후 같이 이동하고 그 위에 쌓는다
board[next_r][next_c].extend(reversed(board[r][c][idx:]))
for _ in range(idx, len(board[r][c])):
horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
del board[r][c][-1]
if len(board[next_r][next_c]) >= 4:
four = True
break
elif color[next_r][next_c] == BLUE: # 방향을 반대로 바꾸고 한 칸 이동한다
if direct == 1 or direct == 3:
next_d = direct + 1
elif direct == 2 or direct == 4:
next_d = direct - 1
next_r, next_c = r + dx[next_d], c + dy[next_d]
if 0 <= next_r < N and 0 <= next_c < N:
if color[next_r][next_c] != BLUE:
if color[next_r][next_c] == WHITE:
board[next_r][next_c].extend(board[r][c][idx:])
elif color[next_r][next_c] == RED:
board[next_r][next_c].extend(reversed(board[r][c][idx:]))
for i in range(idx, len(board[r][c])):
horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
del board[r][c][-1]
horse[num_horse] = [next_r, next_c, next_d]
if len(board[next_r][next_c]) >= 4:
four = True
break
horse[num_horse][DIRECT] = next_d # 이동했건 안했던 일단 방향은 바뀐다
else: # 칸을 벗어나려는 경우 파랑과 같이 처리한다
if direct == 1 or direct == 3:
next_d = direct + 1
elif direct == 2 or direct == 4:
next_d = direct - 1
next_r, next_c = r + dx[next_d], c + dy[next_d]
if color[next_r][next_c] != BLUE:
if color[next_r][next_c] == WHITE:
board[next_r][next_c].extend(board[r][c][idx:])
elif color[next_r][next_c] == RED:
board[next_r][next_c].extend(reversed(board[r][c][idx:]))
for i in range(idx, len(board[r][c])):
horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
del board[r][c][-1]
if len(board[next_r][next_c]) >= 4:
four = True
break
horse[num_horse][DIRECT] = next_d # 이동했건 안했던 일단 방향은 바뀐다
if four:
return t + 1 # t = 0부터 시작이므로 +1해서 리턴
return -1
dx = (0, 0, 0, -1, 1)
dy = (0, 1, -1, 0, 0)
R, C, DIRECT = 0, 1, 2
WHITE, RED, BLUE = 0, 1, 2
input = sys.stdin.readline
N, K = map(int, input().split()) # N=체스판의 크기,K=말의 개수
color = [list(map(int, input().split())) for _ in range(N)] # 색깔판
board = [[[] for _ in range(N)] for _ in range(N)] # 체스판 위에 올라가 있는 말들이 저장될 리스트
horse = [] # 0~K-1번의 말들의 정보가 저장되는 리스트. '0'~'K-1'번을 말들의 번호라고 한다.
for k in range(K):
i, j, d = map(int, input().split()) # row, col, 방향
board[i-1][j-1] = [k] # k=말의 번호. 여러 말이 저장될 수 있으므로 리스트로 저장한다
horse.append([i-1, j-1, d]) # [row, col, 방향 d]
print(solve())
'알고리즘 > 시뮬레이션' 카테고리의 다른 글
| 3190번. 뱀 (0) | 2020.05.04 |
|---|---|
| 17822번. 원판 돌리기 (0) | 2020.05.02 |
| 17140번. 이차원 배열과 연산 (0) | 2020.04.27 |
| SWEA 2382번. 미생물 격리 (0) | 2020.04.24 |
| 17144번. 미세먼지 안녕! (0) | 2020.04.21 |
