문제
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
- A번 말이 이동하려는 칸이
- 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
- 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
- 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
- A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
- A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
- 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
- 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
입력
첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.
다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.
출력
게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.
접근
문제에서 핵심은 말을 이동할 때 위에 있는 말까지 엎어져서 같이 이동하는 것이다. 이 조건만 빼면 다른 조건은 쉽게 구현할 수 있다고 생각한다. 또한 말이 이동할 때 이동하려는 칸의 색깔에 따라서 같이 이동한 말들을 다르게 놓아야하는 것이다.
먼저 함께 말을 이동하는 것을 구현하기 위해 deque라는 자료구조를 사용하였다. 만약 이동하려는 말 위에 다른 말들이 놓여져있다면 deque에 넣는다. 이후 다음으로 이동하는 칸이 흰색일 경우 popleft를 통해 먼저 넣은 말들부터 꺼내고 빨간색일 경우 pop을 통해 나중에 넣은 말부터 꺼내어 놓는다.(빨간색일 경우 뒤집어서 놓아야하기 때문)
이제 어떻게 해당 말 위에 다른 말이 있는지 판단할지 생각해보아야했다.
게임은 말들이 4개 이상 겹쳐져있을 때 종료된다고 하였다. 따라서 5xNxN 짜리 3차원 리스트를 생성하였다. 5라는 숫자가 나온 이유는 0번 인덱스에 해당 좌표에 있는 말들의 개수가 담겨져있고 1번 ~ 4번까지 말들의 번호를 추가하였다.
이제 말들이 순서대로 이동할 때 해당 좌표에서 다음 인덱스에 말이 있는지 판단하여 있을 때 deque에 넣도록 하였다.
구현
- board에는 맵의 색깔을 표시한다.
- move_map에는 해당 좌표에서 말들의 개수와 말들의 번호를 넣는다.
- 이제 K개의 말에 대한 정보를 입력받고 말들을 horses라는 리스트에 넣고
- move_map에 대한 정보를 갱신한다.
N, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move_map = [[[0 for _ in range(5)] for _ in range(N)] for _ in range(N)]
horses = [[-1, -1, -1],]
dy = [0, 0, 0, -1, 1]
dx = [0, 1, -1, 0, 0]
for number in range(K):
y, x, d = map(int, input().split())
y -= 1
x -= 1
horses.append([y, x, d])
move_map[y][x][0] += 1
size = move_map[y][x][0]
move_map[y][x][size] = number + 1- 1000번을 넘어갈 때는 -1이 출력되어야하기 때문에
- turn이 1000이하일 때는 계속해서 반복하도록 하였다.
turn = 1
while turn <= 1000:
if move():
break
turn += 1- 다음은 각 턴마다 말들이 순서대로 이동하는 것을 구현하였다.
- 먼저 말들을 순서대로 꺼낸다음 말이 현재 있는 위치에서 move_map을 조사한다.
- 자신을 포함하여 위에 있는 말들을 deque에 넣는다.
- 동시에 해당 자리에 0을 놓어 비어있다는 것을 표시하고 해당 좌표의 말의 개수를 감소시킨다.
- 그 다음 다음 위치를 탐색하고
- 하얀색일 경우 popleft, 빨간색일 경우 pop하여 말들을 놓는다.
- 해당 과정이 종료되었을 때 말의 개수가 4개 이상일 때 True를 반환하여 게임이 종료되도록 한다.
def move():
for horse in range(1, K+1):
cy, cx, cd = horses[horse][0], horses[horse][1], horses[horse][2]
dq = deque()
for i in range(1, 5):
if move_map[cy][cx][i] == horse:
j = i
while move_map[cy][cx][j] != 0 and j <= 4:
dq.append(move_map[cy][cx][j])
move_map[cy][cx][j] = 0
move_map[cy][cx][0] -= 1
j += 1
break
# 다음 위치 탐색
ny = cy + dy[cd]
nx = cx + dx[cd]
# 맵을 벗어나거나 파란색일 경우
# 방향을 바꿔 다음 위치를 다시 조사한다.
if check_range(ny, nx) == False or board[ny][nx] == 2:
cd = change_direction(cd)
ny = cy + dy[cd]
nx = cx + dx[cd]
horses[horse][2] = cd
# 방향을 바꾼 후에도 다음 위치가 맵을 벗어나거나 파란색일 경우
# 다시 제자리에 말들을 놓는다
if check_range(ny, nx) == False or board[ny][nx] == 2:
size = move_map[cy][cx][0]
size += 1
while size <= 4 and dq:
number = dq.popleft()
move_map[cy][cx][size] = number
horses[number][0], horses[number][1] = cy, cx
size += 1
size -= 1
if size >= 4:
return True
move_map[cy][cx][0] = size
# 다음 위치가 하얀색일 경우
elif board[ny][nx] == 0:
size = move_map[ny][nx][0]
size += 1
while size <= 4 and dq:
number = dq.popleft()
move_map[ny][nx][size] = number
horses[number][0], horses[number][1] = ny, nx
size += 1
size -= 1
if size >= 4:
return True
move_map[ny][nx][0] = size
# 다음 위치가 빨간색일 경우
elif board[ny][nx] == 1:
size = move_map[ny][nx][0]
size += 1
while size <= 4 and dq:
number = dq.pop()
move_map[ny][nx][size] = number
horses[number][0], horses[number][1] = ny, nx
size += 1
size -= 1
if size >= 4:
return True
move_map[ny][nx][0] = size
return False전체 코드
import sys
from _collections import deque
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < N) and (0 <= x < N)
def change_direction(d):
if d == 1:
return 2
elif d == 2:
return 1
elif d == 3:
return 4
else:
return 3
def move():
for horse in range(1, K+1):
cy, cx, cd = horses[horse][0], horses[horse][1], horses[horse][2]
dq = deque()
for i in range(1, 5):
if move_map[cy][cx][i] == horse:
j = i
while move_map[cy][cx][j] != 0 and j <= 4:
dq.append(move_map[cy][cx][j])
move_map[cy][cx][j] = 0
move_map[cy][cx][0] -= 1
j += 1
break
# 다음 위치 탐색
ny = cy + dy[cd]
nx = cx + dx[cd]
if check_range(ny, nx) == False or board[ny][nx] == 2:
cd = change_direction(cd)
ny = cy + dy[cd]
nx = cx + dx[cd]
horses[horse][2] = cd
if check_range(ny, nx) == False or board[ny][nx] == 2:
size = move_map[cy][cx][0]
size += 1
while size <= 4 and dq:
number = dq.popleft()
move_map[cy][cx][size] = number
horses[number][0], horses[number][1] = cy, cx
size += 1
size -= 1
if size >= 4:
return True
move_map[cy][cx][0] = size
elif board[ny][nx] == 0:
size = move_map[ny][nx][0]
size += 1
while size <= 4 and dq:
number = dq.popleft()
move_map[ny][nx][size] = number
horses[number][0], horses[number][1] = ny, nx
size += 1
size -= 1
if size >= 4:
return True
move_map[ny][nx][0] = size
elif board[ny][nx] == 1:
size = move_map[ny][nx][0]
size += 1
while size <= 4 and dq:
number = dq.pop()
move_map[ny][nx][size] = number
horses[number][0], horses[number][1] = ny, nx
size += 1
size -= 1
if size >= 4:
return True
move_map[ny][nx][0] = size
return False
N, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move_map = [[[0 for _ in range(5)] for _ in range(N)] for _ in range(N)]
horses = [[-1, -1, -1],]
dy = [0, 0, 0, -1, 1]
dx = [0, 1, -1, 0, 0]
for number in range(K):
y, x, d = map(int, input().split())
y -= 1
x -= 1
horses.append([y, x, d])
move_map[y][x][0] += 1
size = move_map[y][x][0]
move_map[y][x][size] = number + 1
turn = 1
while turn <= 1000:
if move():
break
turn += 1
if turn > 1000:
turn = -1
print(turn)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 17140] 이차원 배열과 연산 (0) | 2021.07.17 |
|---|---|
| [백준 14503] 로봇 청소기 (0) | 2021.07.16 |
| [백준 3190] 뱀 (0) | 2021.07.14 |
| [백준 13418] 학교 탐방하기 (0) | 2021.07.14 |
| [백준 14621] 나만 안되는 연애 (0) | 2021.07.13 |