0. 문제
Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다. 1. A번 말이 이동하려는 칸이 1) 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다. - A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다. - 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다. 2) 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다. - A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다. - A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다. 3) 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. 4) 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 반환하시오. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 반환한다.
입력
각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다. 말의 개수와 체스판의 정보, 현재 말의 위치와 방향을 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 인덱스, 이동 방향이다. 행과 열의 번호는 0부터 시작하고, 이동 방향은 0, 1, 2, 3 이고 0부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
k = 4 # 말의 개수
chess_map = [
[0, 0, 2, 0],
[0, 0, 1, 0],
[0, 0, 1, 2],
[0, 2, 0, 0]
]
start_horse_location_and_directions = [
[1, 0, 0],
[2, 1, 2],
[1, 1, 0],
[3, 0, 1]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
K = 4 # 말의 개수
chess_map = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
start_horse_location_and_directions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
# 이 경우는 2 을 반환해야 합니다!
1. 내 풀이
k = 4 # 말의 개수
chess_map = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
start_horse_location_and_directions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def get_backword_direction(direction):
# 0 -> 1
# 1 -> 0
# 2 -> 3
# 3 -> 2
if direction // 2 == 0:
return direction + 1
else:
return direction - 1
# 말 위 아래에 있는 말
# 2차원 배열 위에 말이 상하 관계로 쌓여 있는 구조
# [ [[0, 1, 2, 3] , False.. ] #행 ... ] -> 0, 0 위치에 0, 1, 2, 3 순서로 말이 쌓여있다.
def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
# 종료조건 : 말이 k개 겹치는 순간 종료,
# 만약 턴이 1000보다 크거나 게임이 종료되지 않는 경우 -1을 반환
turn_count = 0
N = len(game_map)
# 말 상하관계 정보 초기화
horse_packed_info = [[[] for _ in range(N)] for _ in range(N)]
for i in range(k):
horse = horse_location_and_directions[i]
r, c = horse[0], horse[1]
horse_packed_info[r][c].append(i)
while True:
if turn_count > 1000: # 턴이 1000회 이상 지난경우 -1 반환
return -1
for row in horse_packed_info:
for ele in row:
if len(ele) == k:
return turn_count
for i in range(horse_count):
cur_horse = horse_location_and_directions[i]
r, c, d = cur_horse[0], cur_horse[1], cur_horse[2]
mr, mc = r + dr[d], c + dc[d]
# 다음 칸의 색깔
if 0 <= mr < N and 0 <= mc < N and game_map[mr][mc] == 0: # 흰색
# 모든 쌓여 있는 말들의 위치정보 업데이트
# 단, 자기 위에 쌓여 있는 말들의 위치 정보만 업데이트 할 것\
horses = horse_packed_info[r][c]
permit_to_move = False
cur_horse_level = 0
for l in range(len(horses)):
h = horses[l]
if h == i:
cur_horse_level = l
permit_to_move = True
if permit_to_move:
horse_location_and_directions[h][0] = mr
horse_location_and_directions[h][1] = mc
# 상하정보 업데이트
horse_packed_info[r][c] = horses[:cur_horse_level]
for x in horses[cur_horse_level:]:
horse_packed_info[mr][mc].append(x)
elif 0 <= mr < N and 0 <= mc < N and game_map[mr][mc] == 1: # 빨간색
# 이동
horses = horse_packed_info[r][c]
permit_to_move = False
cur_horse_level = 0
for l in range(len(horses)):
h = horses[l]
if h == i:
cur_horse_level = l
permit_to_move = True
if permit_to_move:
horse_location_and_directions[h][0] = mr
horse_location_and_directions[h][1] = mc
# 상하정보 업데이트
horse_packed_info[r][c] = horses[:cur_horse_level]
for _ in range(len(horses[cur_horse_level:])):
x = horses[cur_horse_level:].pop()
horse_packed_info[mr][mc].append(x)
else: # 파란색
nd = get_backword_direction(d)
horse_location_and_directions[i][-1] = nd
nr, nc = r + dr[nd], c + dc[nd]
# 후진 방향으로 이동할 수 있는 경우
if 0 <= nr < N and 0 <= nc < N and game_map[nr][nc] != 2:
horses = horse_packed_info[r][c]
permit_to_move = False
cur_horse_level = 0
for l in range(len(horses)):
h = horses[l]
if h == i:
cur_horse_level = l
permit_to_move = True
if permit_to_move:
horse_location_and_directions[h][0] = nr
horse_location_and_directions[h][1] = nc
# 상하정보 업데이트
horse_packed_info[r][c] = horses[:cur_horse_level]
for x in horses[cur_horse_level:]:
horse_packed_info[nr][nc].append(x)
else:
# 이동할 수 없는 경우 움직이지 않는다.
pass
turn_count += 1
print("정답 = 2 / 현재 풀이 값 = ",
get_game_over_turn_count(k, chess_map, start_horse_location_and_directions)) # 2가 반환 되어야합니다
start_horse_location_and_directions = [
[0, 1, 0],
[1, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
print("정답 = 9 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))
start_horse_location_and_directions = [
[0, 1, 0],
[0, 1, 1],
[0, 1, 0],
[2, 1, 2]
]
print("정답 = 3 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))
2. 강의 풀이
k = 4 # 말의 개수
chess_map = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
start_horse_location_and_directions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def get_reversed_direction(direction):
if direction // 2 == 0:
return direction + 1
else:
return direction - 1
# 말은 순서대로 이동한다 -> 말의 순서에 따라 반복문
# 말이 쌓일 수 있다. -> 쌓이는 말을 저장한다.
# 쌓이 순서대로 이동한다 -> stack 활용
# 쌓인 말 정보는 chess map과 같은 크기의 리스트를 만든다.
def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
n = len(chess_map)
# 초기 말들의 스택 정보 초기화
current_stacked_horse_map = [[[] for _ in range(n)] for _ in range(n)]
for k in range(horse_count):
r, c, d = horse_location_and_directions[k]
current_stacked_horse_map[r][c].append(k)
# 턴 진행
turn_count = 1
while turn_count <= 1000:
for horse_index in range(horse_count):
r, c, d = horse_location_and_directions[horse_index]
new_r, new_c = r + dr[d], c + dc[d]
# 이동할 칸이 파란색인 경우
if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
new_d = get_reversed_direction(d)
new_r, new_c = r + dr[new_d], c + dc[new_d]
horse_location_and_directions[horse_index][2] = new_d
# 가려는 칸이 막혀있을 경우 이동하지 않음
if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
continue
# 움직일 말들 정보 저장 및 r, c 위치 업데이트
moving_horse_index_array = []
for i in range(len(current_stacked_horse_map[r][c])):
if horse_index == current_stacked_horse_map[r][c][i]:
moving_horse_index_array = current_stacked_horse_map[r][c][i:]
current_stacked_horse_map[r][c] = current_stacked_horse_map[r][c][:i]
break
# new_r, new_c 위치로 말 위치, 스택 정보 업데이트
if game_map[new_r][new_c] == 1: # 빨간색 칸인 경우 이동할 말의 순서를 뒤집는다.
moving_horse_index_array = reversed(moving_horse_index_array)
for moving_horse_index in moving_horse_index_array:
current_stacked_horse_map[new_r][new_c].append(moving_horse_index)
# 위치정보 업데이트
horse_location_and_directions[moving_horse_index][0] = new_r
horse_location_and_directions[moving_horse_index][1] = new_c
# 이동 후 종료조건 확인
if len(current_stacked_horse_map[new_r][new_c]) >= 4:
return turn_count
turn_count += 1
return -1
print("정답 = 2 / 현재 풀이 값 = ",
get_game_over_turn_count(k, chess_map, start_horse_location_and_directions)) # 2가 반환 되어야합니다
start_horse_location_and_directions = [
[0, 1, 0],
[1, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
print("정답 = 9 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))
start_horse_location_and_directions = [
[0, 1, 0],
[0, 1, 1],
[0, 1, 0],
[2, 1, 2]
]
print("정답 = 3 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))
3. 정리
문제 유형 : 주어진 알고리즘을 완벽히 구현하기
내 풀이의 문제점 :
본 문제는 게임맵의 색깔에 따라 각 말들의 움직임이 달라진다. 따라서 각 경우에 따라서 말의 움직임을 구현하고자 했다.
하지만 이는 잘못된 접근이다.
내 코드의 길이가 길어지고 읽기 복잡해진 까닭은 가장 구현하기 쉽다고 판단한 판의 색깔 별로 구조를 짰기 때문이다.
이는 결국에 코드를 더 길게 만들고 복잡하게 만드는 결과를 가져왔다.
아래에서와 같이 강의 풀이의 경우에 각 턴 별 변화하는 말들의 위치, 방향, 움직일말을 구현하는데 집중했다.
각 색깔에 해당하는 조건의 경우 따라 말들의 위치, 움직일 말들의 순서가 변화하는 것을 추가하였다.
즉, 구현을 하는데 있어서 가장 핵심이라 여겨지는 관점이 내 풀이의 경우 이동 조건인 반면 강의 풀이의 경우 각 턴별 변화 시킬 데이터임을 확인해 볼 수 있었다.

내 풀이 | 강의 풀이 | |
중심 관점 | 이동 조건에 따른 말들의 움직임 구현 | 말들의 움직임 구현 - 이동 조건별로 추가 |
코드 길이 | 130줄 | 80줄 |
가독성 | 각 조건 별로 코드를 작성해 중복된 코드가 작성되었다. | 각 조건 별 공통된 코드를 중심으로 이동 위치, 이동할 말 순서 등의 정보만 처리해준다. |
4. 회고
- 세부적인 케이스별 분류 구현을 지양한다.
- 여러 조건 상황 보다도 공통된 기능에 집중하며 구현한다.
- 각 조건 별 공통적으로 변화하는 데이터를 인지한다.
- 가장 핵심이 되는 데이터는 입력과 출력이 되는 데이터이다. 위의 경우 말의 위치, 방향, 쌓임 데이터가 어떻게 변해 가는지를 구현해 가는 과정이다. 이전 위치에서 새로운 위치로 변화할 때 필요한 코드를 가장 우선적으로 구현하고 세부적인 케이스들을 끼워 넣는 식으로 구현하는 것이 좋다.
- 이를 통해 반복저인 코드를 줄이고 공통적 기능을 담은 코드를 명확히 하며 각 상황별로 수정하지 않아도 되기 때문에 시간 역시 단축이 될 수 있다.