문제
[백준 19236 청소년 상어] https://www.acmicpc.net/problem/19236
풀이
상어를 0,0에 넣고 먹은 물고기의 방향으로 상어가 바뀐다.
그 뒤 물고기의 이동이 시작되고, 상어의 이동이 있다. 위 문제를 풀기 위해 필요한 함수를 크게 3가지로 정리해보았다.
입력을 정리해 놓은 리스트 : board
####
- 물고기들의 이동을 구현해 board를 바꿔줄 함수
- 상어가 갈 수 있는 곳들을 반환하는 함수
- dfs 함수로 상어가 갈 곳이 있을 때까지 재귀적으로 호출될 함수
! 헷갈렸던 점
- 아직까지 함수의 인수에 리스트가 들어갈 때도 있고 아닐 때도 있는데 모르겠다. (이번 문제는 재귀 호출이 있기에 board를 인수에 넣어준 거 같다.)
- 상어 이동 함수 구현 시에 nx로 x에 방향을 더한 수를 초기화하고 재귀적으로 돌리려 했는데 그럼 dfs에 반환될 값이 애매해졌다. 해서 nx를 굳이 선언하기보다 x를 계속 바꿔주면서 while문 안에서 리스트에 가능한 좌표를 추가하는 방향으로 설계했다.
- 아직까지 완벽하게 한번에 구현하기는 힘들다는 것을 알았다. 문제 맞추는 거만 힌트 보면서 2시간은 쓴 듯
코드
import copy
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1] #index 0은 비우고 다음부터 구현
dy = [0, 0, -1, -1, -1, 0, 1, 1, 1]
d_fish = [0] * 17
board = [[-1] * 4 for _ in range(4)]
for i in range(4):
temp = list(map(int, input().split()))
now_fish = 0
for j in range(8):
if j % 2 == 0:
now_fish = temp[j]
else:
board[i][j // 2] = [now_fish, temp[j]]
# board에 3차원으로 물고기 번호와 방향을 넣어줌
result = 0 # 최종 결과값
def move_shark(board, now_x, now_y):
positions = []
x, y = now_x, now_y
d = board[x][y][1]
for i in range(4):
x = x + dx[d] #자신에게 계속해서 생신
y = y + dy[d]
if x >= 0 and x < 4 and y >= 0 and y < 4:
#벽이 아니고 비어있지 않으면 리스트에 추가
if board[x][y][0] != -1:
positions.append((x, y))
return positions #가능한 좌표 반환
# 물고기의 좌표를 찾는 함수
def find_fish(board, fish):
for i in range(4):
for j in range(4):
if board[i][j][0] == fish:
return (i, j)
return None
def move_fish(board, now_x, now_y):
for i in range(1,17):
if find_fish(board, i) != None: # 물고기가 있으면
x, y = find_fish(board, i)
while True: #물고기 자리 바꿀 때까지 무한 루프
nx = x + dx[board[x][y][1]]
ny = y + dy[board[x][y][1]]
if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 or (nx,ny) == (now_x,now_y):
board[x][y][1] += 1
if board[x][y][1] >= 9:
board[x][y][1] = 1
else:
if board[nx][ny] == -1:
board[nx][ny] = i
else:
board[x][y], board[nx][ny] = board[nx][ny], board[x][y]
break
def dfs(board, now_x, now_y, total):
global result
board = copy.deepcopy(board)
total += board[now_x][now_y][0]
board[now_x][now_y][0] = -1 #먹었으므로 바꿔주기
move_fish(board, now_x, now_y) #물고기 이동
positions = move_shark(board, now_x, now_y)
if len(positions) == 0: #갈 곳이 없으면
result = max(result, total)
return
for nx, ny in positions:
# 재귀 호출
dfs(board, nx, ny, total)
dfs(board, 0, 0, 0)
print(result)