17837: 새로운 게임 2

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

설명

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

핵심 아이디어

• 이 문제는 시뮬레이션 문제로, 주어진 조건을 잘 수행하면 정답 판정을 받을 수 있다. 
• 모든 말에 대해서 이동을 수행 한 후 count 1 증가 시켜주고 턴의 횟수, 즉 count가 1000번이 넘으면 게임을 강제로 종료시킨다. 또한 말을 이동하면서 말이 4개이상 쌓이는 순간(False로 check) count를 출력하고 게임을 종료한다. 

핵심 구현 함수

# 시뮬레이션 구현 함수
def move(h_number): # 이동하려는 말의 번호가 들어온다.
	# 이동하려는 말의 현재 위치와 방향
	x,y,d = horse[h_number]
	# 다음 이동칸 정의
	nx = x + dx[d]
	ny = y + dy[d]
	if nx < 0 or nx >=n or ny < 0 or ny >=n or graph[nx][ny] == 2:
		# 방향을 반대로
		d = change_dir(d)
		# 업데이트
		horse[h_number][2] = d
		# 다음 칸 재정의
		nx = x + dx[d]
		ny = y + dy[d]
		if nx < 0 or nx >=n or ny < 0 or ny >=n or graph[nx][ny] == 2:
			# 이동하지 않는다.
			return True
	# 현재 말~그 위에 쌓였는 말에 대한 정보를 담을 배열
	horse_up = []
	for h_idx, h_n in enumerate(chess[x][y]): # 모든 말을 순회
		if h_n == h_number:
			# 해당 말 위에 있는 말까지 포함해서 저장
			horse_up.extend(chess[x][y][h_idx:])
			# 이동을 위해 현재 chess 정보에서 제거해 준다.
			chess[x][y] = chess[x][y][:h_idx]
			break
	# 다음 칸이 빨간색 체스판이라면 순서를 반대로 돌린다.
	if graph[nx][ny] == 1:
		horse_up = horse_up[-1::-1]
	# 말 이동 시키기
	for h in horse_up: # h: 말의 번호
		# 이동 시킨다.
		horse[h][0], horse[h][1] = nx,ny
		chess[nx][ny].append(h) # 말 ~ 해당 말 위 모든말 한번에 이동
	# 이제 4마리 이상 쌓여 있으면
	if len(chess[nx][ny]) >= 4:
		return False
	return True

1. 이동하려는 다음 칸이 체스판 범위를 넘거가거나 파란색인 경우, change_dir() 함수를 활용하여 방향을 바꾼다. 바꾼 상태에서 다시 다음 칸으로 이동하려고 할 때 또, 범위를 벗어나거나 파란색이면 이동을 하지 않는다.
2. 이동하기 전에 '현재 위치'에서 chess 배열을 통해 horse_up 리스트에 현재 이동하려는 말 그리고 해당 말 위에 있는 말에 대한 정보를 담는다(extend()활용). 또한 말을 이동하기 위해 chess 리스트에서 horse_up에 저장한 말에 대한 정보를 지운다.
3. 만약 이동하려는 칸이 빨간색이면 horse_up 리스트에 들어있는 말의 순서를 뒤바꾼다.
4. 이동하려는 위치에 horse_up 리스트로 '현재 이동하려는 말 + 위에 있는 말의 번호'를 chess판에 넣어주고, 이동된 말들의 위치 정보를 변경해 준다.
5. 이동이 끝났을 때, 쌓인 말이 4개 이상이라면 게임을 종료할 수 있게 False를 반환한다. 

코드 구현

# 맵의 크기와 말의 개수 입력받기
n, k = map(int, input().split())
# 체스판 정보 입력 받기.
# 0: 흰색 1: 빨강 2: 파랑
graph= [list(map(int, input().split())) for _ in range(n)]
# 방향 정의: 동 서 북 남 -> 1 2 3 4
dx = [0,0,-1,1]
dy = [1,-1,0,0]
# 말의 위치와 방향을 담을 리스트
horse = []
# [말의 번호] 를 저장할 리스트
chess = [[[] for _ in range(n)] for _ in range(n)]
for i in range(k):
	x,y,d = map(int, input().split())
	horse.append([x-1,y-1,d-1]) # 인덱스 재조정
	# 체스판 위치에 말의 번호를 저장한다.
	chess[x-1][y-1].append(i)

# 턴 횟수 초기화
count = 0

# 이동 방향을 반대로 바꾸는 함수
def change_dir(d):
	if d in [0, 2]: # 동 북
		d += 1
	elif d in [1, 3]: # 서 남
		d -= 1
	return d

# 말을 이동해서 시뮬레이션 시작
def move(h_num): # 말의 번호가 들어온다.
	x,y,d = horse[h_num] # 해당 번호 말의 현재 위치와 방향
	nx = x + dx[d]
	ny = y + dy[d]
	# 격자 범위를 벗어나거나 파란색인 경우
	if nx < 0 or nx >=n or ny < 0 or ny >=n or graph[nx][ny] == 2:
		# 방향을 반대로 바꾼다.
		d = change_dir(d)
		horse[h_num][2] = d # 방향 업데이트
		nx = x + dx[d]
		ny = y + dy[d]
		# 방향을 반대로 바꾼 후에 다음 칸이 또 파란색이면 이동하지 않고 멈춘다.
		if nx < 0 or nx >=n or ny < 0 or ny >=n or graph[nx][ny] == 2:
			return True
	# 이동하기 전 현재위치에서 chess 배열을 통해 현재 이동하려는 말 그 위에
	# 쌓아져 있는 말에 대한 정보를 horse_up에 저장한다.
	horse_up = []
	# 현재 위치 (x,y)에서 각 말의 '인덱스와 번호'를 순회하면서 제공
	for h_idx, h_n in enumerate(chess[x][y]):
		# 현재 말의 번호가 찾고자 하는 말의 번호와 일치하다면
		if h_n == h_num:
			# 현재 말(h_n)과 그 위에 모든 말들을 horse_up 리스트에 추가
			# chess[x][y][h_idx:] -> 현재 말의 위치(h_idx)에서 리스트의 끝까지
			horse_up.extend(chess[x][y][h_idx:])
			# 현재 이동하려는 말 ~ 그 위에 쌓아져 있는 말에 대한 번호를 지운다.
			chess[x][y] = chess[x][y][:h_idx]
			break
	# 만약 빨간색이라면 즉 1이라면
	if graph[nx][ny] == 1:
		# 현재 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
		horse_up = horse_up[-1::-1] # == horse_up.reverse()
	'''
	이동하려는 위치 nx,ny에 horse_up 리스트로 현재 이동하려는 말~ 그 위에
	쌓여져 있는 말의 번호를 chess판에 넣어주고, horse 배열에 이동된
	말들의 위치 정보를 변경해 준다,
	'''
	# 특정 말과 그 위에 있던 모든 말들을 새로운 위치로 이동시킨다.
	for h in horse_up:
		horse[h][0], horse[h][1] = nx, ny
		# 이동한 후 현재 말의 번호를 저장
		chess[nx][ny].append(h)

	# 만약 쌓여있는 말의 개수가 4개 이상이라면 종료
	if len(chess[nx][ny]) >= 4:
		return False
	return True

while True:
	check = False
	if count > 1000:
		print(-1)
		break
	for i in range(k):
		if move(i) == False: # 강제 종료됐다면
			check = True
			break
	count += 1
	if check: # 이동 했다면
		print(count)
		break

빨간색 공 조건에서 horse_up = horse_up[-1::-1] 대신 reverse() 함수를 사용해도 가능. horse_up.reverse()