[백준 17837번] 새로운 게임 2

문제 보기

이 문제는 알고리즘 분류는 되어있지 않지만, 시뮬레이션 문제라고 생각한다.

갈수록 삼성의 SW 역량 테스트가 점점 어려워지는 게 느껴진다.

개인적으로 문제를 읽자마자 스택/큐의 개념이 떠올랐지만, 막상 파이썬으로 구현하니 스택/큐를 쓸 일이 없었다.

또한 C/C++의 포인터를 쓰고 싶었지만, 파이썬에는 포인터의 개념이 없기 때문에 해결법을 구상하는데 꽤나 오랜 시간이 걸렸다.

 

문제를 풀기 전, 중요한 변수가 3개 있다.

• board_info: 체스판의 색깔 정보를 담고있는 변수
• board: 체스판 위의 체스말 정보를 담고 있는 변수
• chess_pieces: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.)

이를 가지고 문제를 해결하였다.

문제를 푼 로직은 다음과 같다.

1. 체스 말이 다음에 이동할 곳의 정보를 얻는다. (만약 다음 칸이 체스판 바깥이거나 파란색이라면 방향만 바꿔준다.) (51~52번째 줄)
2. 만약 다음에 이동할 칸이 현재 위치와 같다면(= 다음 칸이 체스판 바깥이거나 파란색이라면) 다음 체스 말로 넘어간다. (체스 말의 방향은 1번에서 이미 바뀌었다.) (54~56번째 줄)
3. 현재 칸에서 이동할 말을 기준으로 현재 칸에 있는 체스 말들을 이등분한다. (58~60번째 줄)
4. 만약 다음에 이동할 칸이 흰색이라면 체스말들을 옮기고, 체스 말들의 위치를 업데이트한다.(= chess_pieces의 값을 업데이트한다.) (62~67번째 줄)
5. 만약 다음에 이동할 칸이 빨간색이라면 체스말들의 순서를 뒤집어서 옮기고, 체스말들의 위치를 업데이트한다. (68~73번째 줄)
6. 만약 체스 말을 옮긴 곳에 체스 말이 4개 이상이라면 현재 턴을 출력하고 종료한다.
7. 각 턴마다 모든 체스 말에 대해 위 작업을 반복하고, 턴이 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)