청소년 상어 [백준 19236]

문제

---

[백준 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)