문제 접근
위의 체스판에서 방향을 가지고 체스를 움직이면서 한칸에 말이 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위치에 있는 말들을 b위치로 이동시키고 말들의 위치를 적어놓은 horse 리스트를 업데이트 하는 것이고
두번째는 이동하려는 위치가 파란색일 때이다.
문제에서 체스판을 벗어나는 경우도 파란색과 같은 경우로 생각했기 때문에 그 경우에도 파란색 칸에서 실행하는 함수를 실행해주면 된다.
문제 풀이
말들을 이동하는 함수
moved_list는 이동하고자 하는 말들의 스택이다. 이동하는 말의 위에 얹혀있는 말들을 구하는 방법은 아래와 같다. 말들의 위치를 담아놓은 game에서 리스트 슬라이싱을 통해 지금 움직이고자 하는 말 위에 있는 말들을 구해준다.
on_i = game[x][y][game[x][y].index(i):]
이렇게 구한 말들의 리스트를 moved라는 함수에 매개변수로 넣고 이동하고자 하는 위치와 현재 위치를 넣는다.
아래와 같이 현재 위치에서의 stack에 담겨있는 이동할 말들은 제거하고 이동할 위치에 이를 append한다. 이렇게 이동한 후에 말들의 위치를 담고 있는 horse를 업데이트 해준다.
def moved(moved_list, next_loc, loc): # 이동시키기
while moved_list:
moving_i = moved_list.pop()
game[loc[0]][loc[1]].pop() # 원래 위치에서 제거
game[next_loc[0]][next_loc[1]].append(moving_i) # 다음 위치로 이동
horse[moving_i] = [next_loc[0], next_loc[1], horse[moving_i][2]]
# 이동한 후 말들의 위치 업데이트파란색일 경우
파란색일 경우에는 방향이 반대로 바뀌어야 한다. 방향이 바뀐 후에 일을 아래의 함수에서 수행하고 있다.
def ifblue(x, y, d, i): # 파란색이라면
nx = x + direct[d][0]
ny = y + direct[d][1]
if nx < 0 or ny<0 or nx>=N or ny>=N or pan[nx][ny] == 2:
# horse 업데이트 하고 가만히
return
else:
on_i = game[x][y][game[x][y].index(i):]
if pan[nx][ny] == 1:
moved(on_i, [nx,ny], [x,y])
else:
on_i.reverse()
moved(on_i, [nx,ny], [x,y])main 코드
answer = -1
direct = [[0,1], [0,-1], [-1,0], [1,0]]
index = 0
flag = False
while index <= 1000:
index += 1
# 구현
# 말의 이동
for i, val in enumerate(horse):
x,y,d = val
nx = x + direct[d][0]
ny = y + direct[d][1]
if nx < 0 or ny<0 or nx>=N or ny>=N or pan[nx][ny] == 2:
if d%2==1: # 방향 바꾸기
d -= 1
else:
d += 1
horse[i] = [x, y, d] #방향을 바꿔줬기 때문에 horse 업데이트
ifblue(x, y, d, i)
else:
# 말의 위에 위치한 말들을 찾고
on_i = game[x][y][game[x][y].index(i):]
if pan[nx][ny] == 1:
moved(on_i, [nx,ny], [x,y])
else:
on_i.reverse()
moved(on_i, [nx,ny], [x,y])
# 종료 조건
for i in range(N):
for j in range(N):
if len(game[i][j]) >= 4:
answer = index
flag = True
break
if flag == True:
break
print(answer)
제출 코드
import sys
N, K = map(int, sys.stdin.readline().split())
pan = []
game = [[[] for j in range(N)] for i in range(N)]
def moved(moved_list, next_loc, loc): # 이동시키기
while moved_list:
moving_i = moved_list.pop()
game[loc[0]][loc[1]].pop() # 원래 위치에서 제거
game[next_loc[0]][next_loc[1]].append(moving_i) # 다음 위치로 이동
horse[moving_i] = [next_loc[0], next_loc[1], horse[moving_i][2]] # 이동한 후 말들의 위치 업데이트
def ifblue(x, y, d, i): # 파란색이라면
nx = x + direct[d][0]
ny = y + direct[d][1]
if nx < 0 or ny<0 or nx>=N or ny>=N or pan[nx][ny] == 2:
# horse 업데이트 하고 가만히
return
else:
on_i = game[x][y][game[x][y].index(i):]
if pan[nx][ny] == 1:
moved(on_i, [nx,ny], [x,y])
else:
on_i.reverse()
moved(on_i, [nx,ny], [x,y])
for i in range(N):
line = list(map(int, sys.stdin.readline().split()))
pan.append(line)
# 0은 흰색, 1은 빨간색, 2는 파란색
horse = []
for i in range(K):
x, y, d = map(int, sys.stdin.readline().split())
horse.append([x-1,y-1,d-1])
game[x-1][y-1].append(i)
# d => 오왼위아래
answer = -1
direct = [[0,1], [0,-1], [-1,0], [1,0]]
index = 0
flag = False
while index <= 1000:
index += 1
# 구현
# 말의 이동
for i, val in enumerate(horse):
x,y,d = val
nx = x + direct[d][0]
ny = y + direct[d][1]
if nx < 0 or ny<0 or nx>=N or ny>=N or pan[nx][ny] == 2:
if d%2==1:
d -= 1
else:
d += 1
horse[i] = [x, y, d]
ifblue(x, y, d, i)
else:
# 말의 위에 위치한 말들을 찾고
on_i = game[x][y][game[x][y].index(i):]
if pan[nx][ny] == 1:
moved(on_i, [nx,ny], [x,y])
else:
on_i.reverse()
moved(on_i, [nx,ny], [x,y])
# 종료 조건
for i in range(N):
for j in range(N):
if len(game[i][j]) >= 4:
answer = index
flag = True
break
if flag == True:
break
print(answer)
