개인적으로 문제를 읽자마자 스택/큐의 개념이 떠올랐지만, 막상 파이썬으로 구현하니 스택/큐를 쓸 일이 없었다.
또한 C/C++의 포인터를 쓰고 싶었지만, 파이썬에는 포인터의 개념이 없기 때문에 해결법을 구상하는데 꽤나 오랜 시간이 걸렸다.
문제를 풀기 전, 중요한 변수가 3개 있다.
board_info: 체스판의 색깔 정보를 담고있는 변수
board: 체스판 위의 체스말 정보를 담고 있는 변수
chess_pieces: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.)
이를 가지고 문제를 해결하였다.
문제를 푼 로직은 다음과 같다.
체스 말이 다음에 이동할 곳의 정보를 얻는다. (만약 다음 칸이 체스판 바깥이거나 파란색이라면 방향만 바꿔준다.) (51~52번째 줄)
만약 다음에 이동할 칸이 현재 위치와 같다면(= 다음 칸이 체스판 바깥이거나 파란색이라면) 다음 체스 말로 넘어간다. (체스 말의 방향은 1번에서 이미 바뀌었다.) (54~56번째 줄)
현재 칸에서 이동할 말을 기준으로 현재 칸에 있는 체스 말들을 이등분한다. (58~60번째 줄)
만약 다음에 이동할 칸이 흰색이라면 체스말들을 옮기고, 체스 말들의 위치를 업데이트한다.(= chess_pieces의 값을 업데이트한다.) (62~67번째 줄)
만약 다음에 이동할 칸이 빨간색이라면 체스말들의 순서를 뒤집어서 옮기고, 체스말들의 위치를 업데이트한다. (68~73번째 줄)
만약 체스 말을 옮긴 곳에 체스 말이 4개 이상이라면 현재 턴을 출력하고 종료한다.
각 턴마다 모든 체스 말에 대해 위 작업을 반복하고, 턴이 1000 이상이면 -1을 출력한다. (48~50번째 줄, 79번째 줄)
3번부터 5번의 과정을 그림으로 요약하자면 다음과 같다.
체스판의 파란색 칸은 2번 과정을 실행하면서 자동으로 처리된다. (이는 코드의 흐름을 따라가다 보면 이해할 수 있다.)
중요한 점은, 체스 말을 이동시키고 chess_pieces 리스트 안에 있는 체스 말의 정보도 업데이트해주어야 한다.
백준에서 프로그램을 종료할 때, exit()를 호출하였는데 자꾸 런타임 에러가 떴다. 구글링을 해보니 sys.exit(0)을 호출해야 런타임 에러 없이 정상적으로 채점이 되는 것 같다.
import sys
n, k = map(int, sys.stdin.readline().split())
board_info = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
board = [[list() for _ in range(n + 1)] for _ in range(n + 1)]
chess_pieces = [0]
# initial board information
for i in range(1, n + 1):
line = list(map(int, sys.stdin.readline().split()))
for j in range(1, n + 1):
board_info[i][j] = line[j - 1]
# initial chess pieces and board
for idx in range(1, k + 1):
r, c, direction = map(int, sys.stdin.readline().split())
chess_pieces.append([r, c, direction])
board[r][c].append(idx)
# returns false if it's blue or out of boundary
def boundary_and_blue_check(_r, _c):
if _r < 1 or _r > n or _c < 1 or _c > n:
return False
if board_info[_r][_c] == 2:
return False
return True
# returns current position if it's blue or out of boundary
def get_next_pos(_r, _c, _d):
next_r, next_c, next_d = _r, _c, _d
# if next position is white or red
if boundary_and_blue_check(next_r + directions[next_d][0], next_c + directions[next_d][1]):
next_r, next_c = next_r + directions[next_d][0], next_c + directions[next_d][1]
# if next position is blue or out of boundary
else:
next_d = next_d + 1 if next_d % 2 else next_d - 1
# if next position is white or red
if boundary_and_blue_check(next_r + directions[next_d][0], next_c + directions[next_d][1]):
next_r, next_c = next_r + directions[next_d][0], next_c + directions[next_d][1]
return next_r, next_c, next_d
directions = ((), (0, 1), (0, -1), (-1, 0), (1, 0))
turn = 0
while turn <= 1000:
turn += 1
for idx, piece in list(enumerate(chess_pieces))[1:]:
r, c, d = chess_pieces[idx][0], chess_pieces[idx][1], chess_pieces[idx][2]
next_r, next_c, chess_pieces[idx][2] = get_next_pos(r, c, d)
# no need to move chess pieces because it's blue or out of boundary
if r == next_r and c == next_c:
continue
# split chess pieces into 2
base_index = board[r][c].index(idx)
board[r][c], temp_list = board[r][c][:base_index], board[r][c][base_index:]
# white
if board_info[next_r][next_c] == 0:
# move and update position of chess pieces
board[next_r][next_c].extend(temp_list)
for i in temp_list:
chess_pieces[i][0], chess_pieces[i][1] = next_r, next_c
# red
elif board_info[next_r][next_c] == 1:
# move and update position of chess pieces
board[next_r][next_c].extend(reversed(temp_list))
for i in temp_list:
chess_pieces[i][0], chess_pieces[i][1] = next_r, next_c
if len(board[next_r][next_c]) >= 4:
print(turn)
sys.exit(0)
print(-1)
