알고리즘
[알고리즘_코드리뷰] 삼성역량테스트- 구슬탈출
개발자명백
2023. 5. 17. 00:58
0. 문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다. 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
보드를 나타내는 2차원 배열 game_map이 주어진다. 이 때, 보드의 행, 열의 길이는 3이상 10 이하다. 보드 내에 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다.
game_map = [
["#", "#", "#", "#", "#"],
["#", ".", ".", "B", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
] # -> True를 반환해야 한다.
game_map = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "R", "#", ".", ".", ".", "#", "#", "B", "#"],
["#", ".", ".", ".", "#", ".", "#", "#", ".", "#"],
["#", "#", "#", "#", "#", ".", "#", "#", ".", "#"],
["#", ".", ".", ".", ".", ".", ".", "#", ".", "#"],
["#", ".", "#", "#", "#", "#", "#", "#", ".", "#"],
["#", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
["#", ".", "#", ".", "#", ".", "#", ".", ".", "#"],
["#", ".", ".", ".", "#", ".", "O", "#", ".", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
] # -> False 를 반환해야 한다
1. 첫 시도 -> 잘못된 풀이
# 잘못된 풀이
from collections import deque
game_map = [
["#", ".", ".", "B", "#"],
["#", "#", "#", "#", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
# 모든 경우를 탐색해야 한다.
# 자료구조 : visited 2차원배열, queue (rr, cr, rb, cb) -> 동시에 움직임
# 알고리즘 : bfs
# 탈출조건 : 파란구슬이 도달하기 전 빨간 구슬이 구멍에 도달할 경우 종료한다.
# 이동조건 : ->, <-, 아래, 위 일 때
# 이동을 10번 이하로 빨간구슬을 빼낼 수 있는지 구하는 프로그램을 구하시오
# 빨간구슬의 이동방향이 바뀌는 횟수를 카운트. 오직 빨간 구슬의 방문 여부만 중요하다.
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
def is_available_to_take_out_only_red_marble(game_map):
n, m = len(game_map), len(game_map[0])
visited = [[False for _ in range(m)] for _ in range(n)]
queue = deque()
rr, cr, rb, cb, ro, co = 0, 0, 0, 0, 0, 0
# R, B 초기위치
for r in range(n):
for c in range(m):
if game_map[r][c] == 'R':
rr, cr = r, c
elif game_map[r][c] == 'B':
rb, cb = r, c
elif game_map[r][c] == 'O':
ro, co = r, c
queue.append((rr, cr, rb, cb))
level = 0
while queue:
for _ in range(len(queue)):
rr, cr, rb, cb = queue.popleft()
visited[rr][cr] = True
# 탐색 -> 해당 방향으로 끝까지 이동시켜야 합니다.
for i in range(4):
nrr, ncr = rr + dr[i], cr + dc[i]
nrb, ncb = rb + dr[i], cb + dc[i]
# 종료조건 : 파란 공이 구멍에 먼저 도달한 경우
if nrb == ro and ncb == co:
return False
# 종료조건 : 빨간공이 구멍에 도달한 경우
if nrr == ro and ncr == co:
# 방향 i를 유지 했을 때 B도 구멍에 들어간다면 실패
while game_map[nrb][ncb] != '#':
nrb, ncb = nrb + dr[i], ncb + dc[i]
if nrb == ro and ncb == co:
return False
# i 방향으로 B를 끝까지 굴렸을 때 구멍에 도달하지 않는 경우에만 True
return True
# R이 갈 수 있는 위치
if 0 < nrr < n - 1 and 0 < ncr < m - 1 and game_map[nrr][ncr] != '#' and not visited[nrr][ncr]:
# R이 가려는 위치에 B가 있고, B가 가려는 방향이 열려 있다면 이동할 수 있음
if nrr == rb and ncr == cb :
if game_map[nrb][ncb] != '#':
# b의 진행 방향이 막힌 경우 -> 탐색 불가
# b의 진행 방향이 막혀있지 않은 경우 -> 탐색 가능
queue.append((nrr, ncr, nrb, ncb))
else : # r이 가는 위치는 열려 있고 B가 있지 않은 경우
# b의 다음 위치가 열린 경우 -> 함께 이동
if game_map[nrb][ncb] != '#':
queue.append((nrr, ncr, nrb, ncb))
else: # b의 다음 위치가 벽인 경우 -> b의 위치 고정
queue.append((nrr, ncr, rb, cb))
# b의 다음 위치가 R인 경우 -> r이 움직일 수 있는 경우로 제한했기 때문에 추산하지 않음
level += 1
return False
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
2. 내 풀이 -> 정답
from collections import deque
game_map = [
["#", ".", ".", "B", "#"],
["#", "#", "#", "#", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
# 모든 경우를 탐색해야 한다.
# 자료구조 : visited 2차원배열, queue (rr, cr, rb, cb) -> 동시에 움직임
# 알고리즘 : bfs
# 탈출조건 : 파란구슬이 도달하기 전 빨간 구슬이 구멍에 도달할 경우 종료한다.
# 이동조건 : ->, <-, 아래, 위 일 때
# 이동을 10번 이하로 빨간구슬을 빼낼 수 있는지 구하는 프로그램을 구하시오
# 빨간구슬의 이동방향이 바뀌는 횟수를 카운트. 오직 빨간 구슬의 방문 여부만 중요하다.
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
def is_available_to_take_out_only_red_marble(game_map):
n, m = len(game_map), len(game_map[0])
visited = [[False for _ in range(m)] for _ in range(n)]
queue = deque()
rr, cr, rb, cb, ro, co = 0, 0, 0, 0, 0, 0
# R, B 초기위치
for r in range(n):
for c in range(m):
if game_map[r][c] == 'R':
rr, cr = r, c
elif game_map[r][c] == 'B':
rb, cb = r, c
elif game_map[r][c] == 'O':
ro, co = r, c
queue.append((rr, cr, rb, cb))
visited[rr][cr] = True
level = 1
while queue:
if level > 10:
return False
for _ in range(len(queue)):
rr, cr, rb, cb = queue.popleft()
# 탐색 -> 해당 방향으로 끝까지 이동 시켜야 합니다.
for i in range(4):
nrr, ncr = rr + dr[i], cr + dc[i]
nrb, ncb = rb + dr[i], cb + dc[i]
R_met_O, B_met_O = False, False
# R이 갈 수 있는 위치인 경우
while 0 < nrr < n - 1 and 0 < ncr < m - 1 and game_map[nrr][ncr] != '#' and not visited[nrr][ncr]:
visited[nrr][ncr] = True
# 새로운 위치에서 빨간구슬 혹은 파란 구슬이 구멍에 도달한 경우 -> 종료조건
if nrr == ro and ncr == co:
R_met_O = True
if nrb == ro and ncb == co:
B_met_O = True
# 파란 구슬의 다음 위치가 진행할 수 있는 경우 빨간 구슬 파란 구슬의 다음 위치 업데이트
if 0 < nrb < n - 1 and 0 < ncb < m - 1 and game_map[nrb][ncb] != '#':
nrb, ncb = nrb + dr[i], ncb + dc[i]
nrr, ncr = nrr + dr[i], ncr + dc[i]
# 빨간 구슬의 다음 위치가 파란 구슬로 막혀 있지 않은 경우에 빨간 구슬의 다음 위치 업데이트
elif not (nrr == nrb - dr[i] and ncr == ncb - dc[i]):
nrr, ncr = nrr + dr[i], ncr + dc[i]
# 만약 파란 구슬의 진행이 남은 경우 파란 구슬의 다음 위치 업데이트
while 0 < nrb < n - 1 and 0 < ncb < m - 1 and game_map[nrb][ncb] != '#' and not (
nrb == nrr - dr[i] and ncb == ncr - dc[i]):
if nrb == ro and ncb == co:
B_met_O = True
nrb, ncb = nrb + dr[i], ncb + dc[i]
# 큐에 현재 위치 삽입
queue.append((nrr - dr[i], ncr - dc[i], nrb - dr[i], ncb - dc[i]))
if R_met_O:
if level <= 10 and not B_met_O:
return True
else:
return False
level += 1
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", "R", "B", ".", ".", ".", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", "O", "#", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
3. 강의 정답
# 강의 정답
from collections import deque
game_map = [
["#", "#", "#", "#", "#"],
["#", ".", ".", "B", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
# 문제 해결에 규칙성을 찾기 힘들기 때문에 탐색해 나갑니다. 모든 경우를 시도해 보면서 탈출 할 수 있는 경우를 탐색합니다.
# 즉, bfs를 사용하며 큐로 구현합니다.
# 방문여부 : visited -> 공이 2개입니다. 방문 여부를 어떻게 확인할 것인가??
# => 4차원 배열 visited[빨간공의 row][빨간공의 col][파란공의 row][파란공의 col]
# => 행과 열의 길이가 3~10으로 상수이기 때문에 공간복잡도는 상수입니다.
def move_until_wall_or_holl(r, c, diff_r, diff_c, game_map):
move_count = 0
while game_map[r + diff_r][c + diff_c] != "#" and game_map[r][c] != "O":
r += diff_r
c += diff_c
move_count += 1
return r, c, move_count
def is_available_to_take_out_only_red_marble(game_map):
n, m = len(game_map), len(game_map[0])
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
red_row, red_col, blue_row, blue_col = -1, -1, -1, -1
queue = deque()
for i in range(n):
for j in range(m):
if game_map[i][j] == "R":
red_row, red_col = i, j
elif game_map[i][j] == "B":
blue_row, blue_col = i, j
queue.append((red_row, red_col, blue_row, blue_col, 1)) # 탐색할 공들의 위치와 탐색 횟수
visited[red_row][red_col][blue_row][blue_col] = True
while queue:
rr, rc, br, bc, c = queue.popleft()
if c > 10:
break
for i in range(4):
next_red_row, next_red_col, red_move_count = move_until_wall_or_holl(rr, rc, dr[i], dc[i], game_map)
next_blue_row, next_blue_col, blue_move_count = move_until_wall_or_holl(br, bc, dr[i], dc[i], game_map)
if game_map[next_blue_row][next_blue_col] == 'O':
continue
if game_map[next_red_row][next_red_col] == 'O':
return True
# 움직임 후보정 : 두 공이 겹치는 경우 더 많이 움직인 공이 후진합니다.
if next_red_row == next_blue_row and next_red_col == next_blue_col:
if red_move_count > blue_move_count:
next_red_row -= dr[i]
next_red_col -= dc[i]
else:
next_blue_row -= dr[i]
next_blue_col -= dc[i]
# 빨간공과 파란공이 도달한 위치가 아직 방문하지 않은 경우라면 큐에 추가
if not visited[next_red_row][next_red_col][next_blue_row][next_blue_col]:
visited[next_red_row][next_red_col][next_blue_row][next_blue_col] = True
queue.append((next_red_row, next_red_col, next_blue_row, next_blue_col, c + 1))
return False
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", "R", "B", ".", ".", ".", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", ".", "#", "#"],
["#", "#", "#", "#", "O", "#", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
4. 정리
- 첫 시도의 풀이의 경우 문제이해를 잘못하였다. "공의 이동"을 기준으로 수를 센 탓에 예시와 다른 결과값을 도출했다. 공의 움직임을 정지하는 경우가 없기 때문에 "이동"이 공의 이동 거리가 아닌 게임 보드의 방향을 바꾼 횟수였다. 문제를 정독 하더라도 내가 이해하고 있는 상황이 정확한 것인지 점검을 해야 한다. 주어진 예시에 대입해 과연 내가 이해한 것이 맞는 것인지 판단해야한다.
- 문제에서 핵심이 되는 구현은 공이 끝까지 움직이는 부분이다. 공이 벽 끝까지 움직여야 하며 또한 파란공과 빨간 공이 겹쳐서는 안된다. 내 풀이의 경우 파란공과 빨간공이 겹치는 경우 보정을 해주기 위해서 4가지 경우를 따져야 했다. 이처럼 복잡하게 문제가 진행된 까닭은 방문 여부에 파란공을 포함 시키지 않았기 때문이다. 빨간공을 기준으로 파란 공의 움직임을 처리한 터라 코드가 복잡해졌다.
- 강의 풀이의 경우 방문 여부를 4차원 배열을 활용해 저장하였다. 이 덕에 빨간공과 파란공의 두 위치를 모두 저장할 수 있다.
- 강의의 풀이의 경우 '후보정'의 개념을 활용했다. 일단 각 공은 벽에 닿을 때까지 끝까지 이동한다는 공통점을 가진다. 어떤 공이 한 칸 뒤로 갈지를 move_count 를 활용하여 더 많이 움직인 공이 한 칸 뒤로 움직이는 것이다. 이 아이디어를 통해 내 풀이에서는 매우 복잡하게 구현한 후보정 과정을 간단히 구현했다. 즉, 내 풀이에서는 공이 움직이는 모든 순간을 포착하여 빨간공과 파란공의 두 움직임을 동시에 구현했다. 반면 강의 풀이는 빨간공, 파란공에 공통적으로 적용되는 법칙을 적용한 이후 후보정 과정을 통해 이를 단순화 했다.
- 내 풀이의 경우 상황을 복잡하게 만든 원인으로 불필요한 축약을 들 수 있다. 작성이 귀찮다는 연유로 축약된 변수를 사용한 탓에 상황을 이해하기에 더욱 복잡해졌다. 강의 풀이 처럼 보다 직관적으로 이해할 수 있는 변수명을 사용하는 것이 보다 나은 풀이인듯하다.
| 내 풀이 | 강의 풀이 | |
| 주요 관점 | 빨간공을 기준으로 파란공의 움직임을 처리한다. | 빨간공 파란공 움직임 모두를 처리한다. |
| 주요 차이 | 각 공의 개별적인 상황에 맞춰 움직임을 구현한다. | 각 공의 공통적인 법칙에 맞춰 다음 움직임을 적용하고 이후 후보정 과정을 거친다. |
| 변수명 | 변수명에 축약어를 사용한 탓에 직관적인 의미가 와닿지 않아 코드를 재이해하기 어렵다. | 직관적인 변수명을 사용하여 각 기능을 순식간에 이해할 수 있다. |