✏️
문제 풀이
- 델타 이동 구현 + DFS로 풀었다.
- 문제의 요구사항에서 물고기 이동 단계와 상어 이동 단계가 반복되므로 각 단계를 함수로 만들었다.
- 상어 이동 단계는 상어가 이동 가능한 위치가 여러 개 있을 수 있고 모든 경우의 수를 탐색해야 하므로 DFS를 적용하여 재귀적으로 탐색했다.
제출 코드
import sys
import copy
input = sys.stdin.readline
drc = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
arr = [[0] * 4 for _ in range(4)] # 물고기 배치. (fish, direction): 물고기 번호, 방향. 0: 빈자리, -1: 상어
fish_list = [0] * 17 # 물고기 정보. fish_list[i]: i번 물고기의 (방향, r, c) 저장
for r in range(4):
row = list(map(int, input().split()))
for c in range(4):
fish = row[2 * c]
direction = row[2 * c + 1] - 1
arr[r][c] = (fish, direction)
fish_list[fish] = (direction, r, c)
# 물고기 이동 함수
def move_fish(arr, fish_list):
# 1. i: 물고기 번호, 1 ~ 16번 순회
for i in range(1, 17):
if fish_list[i]:
d, r, c = fish_list[i]
# 2. 반시계 방향으로 45도 회전하며 이동 가능한 위치 찾기
for j in range(8):
nd = (d + j) % 8
dr, dc = drc[nd]
nr, nc = r + dr, c + dc
if 0 <= nr < 4 and 0 <= nc < 4 and arr[nr][nc] != -1:
# 3-1. 물고기 없는 칸
if arr[nr][nc] == 0:
arr[nr][nc] = (i, nd)
arr[r][c] = 0
fish_list[i] = (nd, nr, nc)
# 3-2. 물고기 있는 칸: 교환
else:
other_fish, other_d = arr[nr][nc]
# 물고기 배치도 업데이트
arr[r][c] = arr[nr][nc]
arr[nr][nc] = (i, nd)
# 물고기 정보 업데이트
fish_list[other_fish] = (other_d, r, c)
fish_list[i] = (nd, nr, nc)
break
# 상어 이동 DFS 함수
def move_shark(v, arr, fish_list):
global maxV
# 1. 물고기 움직이기
move_fish(arr, fish_list)
# 2. 상어 움직이기
sum_fish, d, r, c = v
dr, dc = drc[d]
arr[r][c] = 0 # 상어 위치 해제
# 2-1. 상어가 이동할 수 있는 위치들 확인
next_spots = []
while True:
r += dr
c += dc
if 0 <= r < 4 and 0 <= c < 4:
if arr[r][c] != 0:
next_spots.append((r, c))
else:
break
# 2-2. 상어 이동
for w in next_spots:
nr, nc = w # 이동할 위치
fish, nd = arr[nr][nc] # 잡아먹힐 물고기 정보
sum_fish += fish
# 바뀐 정보를 기록하기 위해 deepcopy 이용
new_arr = copy.deepcopy(arr)
new_fish_list = copy.deepcopy(fish_list)
new_arr[nr][nc] = -1 # 상어 위치 체크
new_fish_list[fish] = 0 # 잡아 먹힌 물고기 체크
# 2-3. 재귀적으로 탐색
move_shark((sum_fish, nd, nr, nc), new_arr, new_fish_list)
# 2-4. 최대값 갱신
if maxV < sum_fish:
maxV = sum_fish
# 2-5. 다른 위치로 이동 전 초기화
sum_fish -= fish
initial_fish, initial_direction = arr[0][0]
maxV = initial_fish # 상어가 먹은 물고기 합의 최대값. 초기값은 처음 먹은 물고기 번호
arr[0][0] = -1 # 상어 위치 체크
fish_list[initial_fish] = 0 # 처음 먹힌 물고기 체크
move_shark((initial_fish, initial_direction, 0, 0), arr, fish_list)
print(maxV)느낀점 - 파이썬의 동적 타입
이 문제를 풀면서 내가 그동안 구현 문제를 풀 때 파이썬의 동적 타입을 많이 이용하고 있었다는 것을 인지했다.
정적 타입 언어와 동적 타입 언어
- 정적 타입 - 변수에 자료형을 지정해주어야 하며 컴파일 시에 자료형에 맞지 않은 값이 들어있으면 컴파일 에러가 발생한다.
- 동적 타입 - 런타임 시 변수의 타입을 판단하여 지정해 주며 하나의 변수에 다른 자료형의 값을 재할당 가능하다.
본 문제에서는 물고기 배치를 나타낸 2차원 배열을 4*4 정수형 배열로 만들고, 물고기와 상어의 이동에 따라 배열에 저장된 값들을 바꿔주었다. 이때 빈자리는 0, 상어의 자리는 -1을 할당하고 물고기의 자리는 (물고기 번호, 방향)을 저장한 튜플을 할당하였다. 물고기 배치가 바뀌면 2차원 배열의 각 자리에서는 정수가 저장된 자리에 튜플이 재할당되거나 그 반대가 일어날 수 있다. 동적 타입 언어인 파이썬은 이러한 자료 설계가 가능하다.
동적 타입은 매번 변수에 타입을 지정하지 않아도 되고 다른 타입의 값도 할당할 수 있어 간단하고 유연하게 코드를 작성할 수 있다는 장점이 있다. 이는 제한된 시간 내에 빠르게 문제를 풀어야 하는 코딩테스트에서 큰 메리트가 있다고 생각한다.
다만, 협업을 요하는 대규모 서비스에서는 다른 사람이 작성한 변수의 타입을 이해하기 어렵고, 타입 에러를 컴파일 에러가 아닌 런타임 에러로 잡아야하기 때문에 단점이 많을 것 같다.