https://www.acmicpc.net/problem/17837
공부 날짜 : 2022.09.26
정답 참고 여부 : X
체스판과 말이 있으며 각 말이 순서와 방향에 맞게 움직인다. 말이 움직일때 자신보다 위에있는 말은 함께 움직이며 움직이려는 칸의 색에따라 순서가 바뀌며 말이 4개가 한칸에서 만나면 게임이 종료되며 게임이 종료되는 턴을 구하는 문제이다.
푸는 것은 어렵지 않았지만 문제 설명이 애매해서 오래걸린 문제.
이동하려는 칸이 파란or빈칸일때 뒤방향으로 움직이는데 이때는 위에 쌓인 말과 함께 움직이는지 표현이 없어서 그냥 말만 옮겨서 오래 걸렸다.
즉 파란색이라서 뒤로가는데 뒤에칸이 흰색 or 빨간색이므로 마찬가지로 말보다 위에 있는 말들을 모두 움직여야 하는데 파란색이라는 조건이 붙어서 그냥 말만 옮겼다가 한참 디버깅 과정에서 이상함을 느껴 수정했더니 정답으로 나왔다.
자신보다 위에있는 말은 리스트 상에서 자신보다 index가 큰 숫자들로 표현했고 자신의 index에서 리스트의 끝까지 개수를 세서
자신의 인덱스부터 옮길지 끝에서부터 옮길지 정하면 되는 문제였다.
나는
for j in range(len(token_graph[x][y])):
#움직이려는 토큰 번호에서부터
if token_graph[x][y][j] == i:
#끝까지
for _ in range(len(token_graph[x][y])-j):
#토큰 그래프에서 옮기고, 토큰포지션 최신화
move_token = token_graph[x][y].pop(j)
#옮기는 칸이 빨간색인경우
#move_token = token_graph[x][y].pop(-1)
token_graph[nx][ny].append(move_token)
token_postion[move_token][0] = nx
token_postion[move_token][1] = ny
break이처럼 리스트에서 옮기려는 토큰의 index를 구해서 (리스트 길이 - index) 만큼 옮기는 과정을 반복하고 break로 멈춰주었다.
설명이 좀 애매하다고 느끼고 있고 파란색 이동시 층으로 쌓인경우의 예시도 없어서 문제 이해를 제대로 하지못해서 오래 걸렸던 문제.
소스코드
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
#행번호,열번호,이동방향
token_postion = []
#그래프 위치에 쌓여있는 상태를 나타내는 행렬
token_graph = [[[]for _ in range(n)] for _ in range(n)]
for i in range(k):
x,y,dir = map(int, input().split())
token_graph[x-1][y-1].append(i)
token_postion.append([x-1,y-1,dir])
#1,2,3,4이므로 0번은 빈칸으로 0
#방향을 반대로 하기위해 -1,-2,-3,-4,순으로 반대방향이 되도록 작성
dx = [0,0,0,-1,1,-1,1,0,0]
dy = [0,1,-1,0,0,0,0,1,-1]
count = 0
game_clear = False
while True:
#1000번을 넘길경우 -1 출력한뒤 멈춤
if count > 1000:
print(-1)
break
#게임이 클리어 됐으면 턴수만큼 출력하고 멈춤
if game_clear:
print(count)
break
count += 1
#모든 토큰에 대해서/ 현재 움직이는 토큰은 i
for i in range(k):
x,y,dir = token_postion[i]
nx = x + dx[dir]
ny = y + dy[dir]
#범위 밖이거나 파란색이면 방향 반대로 해서 한칸 전진
if nx < 0 or nx >= n or ny < 0 or ny >= n or graph[nx][ny] == 2:
dir *= -1
token_postion[i][2] *= -1
#방향 바꿔서 이동좌표 갱신
nx = x + dx[dir]
ny = y + dy[dir]
#반대방향 한칸 전진시 범위 밖 or 그 칸이 파란색이면 안함
if nx < 0 or nx >= n or ny < 0 or ny >= n or graph[nx][ny] == 2:
#마지막 이동한 위치의 말의 개수를 파악하기 위해 nx,ny가 사용되므로
#안움직이더라도 nx,ny가 현재위치라고 갱신해줌
nx,ny = x,y
#흰색인 경우
elif graph[nx][ny] == 0:
#해당칸에 있는 토큰들에 대해서
for j in range(len(token_graph[x][y])):
#움직이려는 토큰 번호에서부터
if token_graph[x][y][j] == i:
#끝까지
for _ in range(len(token_graph[x][y])-j):
#토큰 그래프에서 옮기고, 토큰포지션 최신화
move_token = token_graph[x][y].pop(j)
token_graph[nx][ny].append(move_token)
token_postion[move_token][0] = nx
token_postion[move_token][1] = ny
break
#빨간색인 경우
elif graph[nx][ny] == 1:
#해당칸에 있는 토큰들에 대해서
for j in range(len(token_graph[x][y])):
#움직이려는 토큰 번호에서부터
if token_graph[x][y][j] == i:
#끝까지 횟수만큼
for _ in range(len(token_graph[x][y])-j):
#토큰 그래프의 뒤에서부터 옮기고, 토큰포지션 최신화
move_token = token_graph[x][y].pop(-1)
token_graph[nx][ny].append(move_token)
token_postion[move_token][0] = nx
token_postion[move_token][1] = ny
break
#흰색인 경우
elif graph[nx][ny] == 0:
#해당칸에 있는 토큰들에 대해서
for j in range(len(token_graph[x][y])):
#움직이려는 토큰 번호에서부터
if token_graph[x][y][j] == i:
#끝까지
for _ in range(len(token_graph[x][y])-j):
#토큰 그래프에서 옮기고, 토큰포지션 최신화
move_token = token_graph[x][y].pop(j)
token_graph[nx][ny].append(move_token)
token_postion[move_token][0] = nx
token_postion[move_token][1] = ny
break
#빨간색인 경우
elif graph[nx][ny] == 1:
#해당칸에 있는 토큰들에 대해서
for j in range(len(token_graph[x][y])):
#움직이려는 토큰 번호에서부터
if token_graph[x][y][j] == i:
#끝까지 횟수만큼
for _ in range(len(token_graph[x][y])-j):
#토큰 그래프의 뒤에서부터 옮기고, 토큰포지션 최신화
move_token = token_graph[x][y].pop(-1)
token_graph[nx][ny].append(move_token)
token_postion[move_token][0] = nx
token_postion[move_token][1] = ny
break
#현재 움직인 칸에 말이 4개 이상 쌓였으면 게임 클리어
if len(token_graph[nx][ny]) >= 4:
game_clear = True
break
