[Python] Baekjoon - 19236. 청소년 상어

백준 19236번 청소년 상어 - 백트래킹과 시뮬레이션을 이용하여 해결해야 하는 문제이다. solved.ac 난이도는 골드 2로, 구현이 꽤나 까다로운 문제였다. 

 

문제 정보

알고리즘 분류

• 백트래킹, 시뮬레이션

난이도

• 골드 2

 

문제 풀이

과정

문제를 딱 본 순간부터 엄청나게 복잡한 문제를 만났구나.. 싶었다. DFS 백트래킹을 통해 문제를 풀어보려고 하는데, 처음에는 현재 상태(물고기 위치, 방향)를 전역 변수로 저장해두도록 구현을 했다. 그렇게 하니 재귀를 빠져나올 때 물고기를 원래 상태로 되돌려 놔야 했다. 숫자가 큰 물고기부터 방향을 반대로 생각하고 되돌려봤는데 처음 상태랑 다른 결과가 나왔다. 물고기가 이동할 수 없을 때 될 때까지 방향을 돌리기 때문에 처음 방향이 어땠는지를 알 방법이 없었다. 따라서 방향 정보는 전역 변수로 사용하지 않고 계속 들고 다니도록 하였다.

 

DFS 재귀함수의 로직

1. 상어가 도착한 위치의 물고기 잡아먹기
2. 물고기 전체 이동
3. 상어가 갈 수 있는 위치에 물고기가 있으면 해당 위치로 이동(재귀 호출)
4. 잡아먹을 물고기가 없었다면 물고기 최대합 갱신하고 집으로 가기
5. 함수 끝나기 전에 물고기 위치 되돌리기

풀이

• 전역변수
  • position_fishes[i]: i번째 물고기의 현재 위치 [r, c] 저장 (잡아먹혔으면 [-1,-1])
  • board[r][c]: 현재 격자 공간의 (r, c) 위치에 있는 물고기의 번호 저장(없으면 0)
• 함수
  • move_fishes(shark_r, shark_c, t, state)
    • 상어가 (shark_r, shark_c) 위치에 있고 물고기들의 방향 정보 state가 주어졌을 때, t=0이면 물고기 전체 이동, t=1이면 물고기 위치를 되돌려 놓는 함수.
    • 이동 후 방향 상태를 반환
  • eat_fish(r, c)
    • 상어가 (r, c) 위치의 물고기를 잡아먹는 함수. 잡아먹힌 물고기의 번호를 반환.
  • repair_fish(r, c, fish)
    • (r, c)의 위치에서 잡아먹혔던 물고기 fish를 다시 되돌리는 함수.
  • dfs(shark, current_sum, state)
    • 상어가 이동하게 된 위치 shark와 현재까지 잡아먹은 물고기 번호의 합 current_sum, 현재 물고기들의 방향 상태 state가 주어졌을 때, 게임을 계속 진행하는 함수
    • 상어가 물고기를 잡아먹은 뒤 물고기들이 이동하고, 상어가 이동할 수 있는 칸으로 이동하며 재귀를 호출하고, 잡아먹을 물고기가 없으면 집에 가며, 함수를 빠져나가기 전에 물고기의 위치를 되돌려놓음

코드

# t(0): 물고기 이동, t(1): 물고기 위치 복구
def move_fishes(shark_r, shark_c,t, state):
    global position_fishes, board, dr, dc

    new_state = [*state]

    if t == 0:
        order = [i for i in range(1,17)]
    else:
        order = [i for i in range(16, 0, -1)]

    # 물고기 차례대로 이동
    for fish in order:
        fish_r, fish_c = position_fishes[fish][0], position_fishes[fish][1]
        fish_d = int(new_state[4*fish_r+fish_c])

        # 이미 잡아먹힌 물고기면 패스
        if (fish_r, fish_c) == (-1,-1):
            continue

        cnt = 0
        while True:
            # 모든 방향으로 이동할 수 없는 경우 패스
            if cnt == 8:
                break

            there_r, there_c = fish_r + dr[t][fish_d], fish_c + dc[t][fish_d]

            # 이동할 수 있는 칸일 때
            if 0 <= there_r < 4 and 0 <= there_c < 4 and (there_r, there_c) != (shark_r, shark_c):
                there_fish = board[there_r][there_c]

                # 이동할 칸으로 자리 교환
                board[fish_r][fish_c] = there_fish
                board[there_r][there_c] = fish
                position_fishes[fish] = [there_r, there_c]
                position_fishes[there_fish] = [fish_r, fish_c]
                new_state[4*fish_r+fish_c], new_state[4*there_r+there_c] = new_state[4*there_r+there_c], str(fish_d)
                break

            # 이동할 수 없는 칸이면 45도 회전
            else:
                fish_d += 1
                if fish_d == 9:
                    fish_d = 1
                cnt += 1

    return ''.join(new_state)


def eat_fish(r, c):
    global position_fishes, board

    eaten_fish = board[r][c]
    board[r][c] = 0
    position_fishes[eaten_fish] = [-1, -1]

    return eaten_fish


def repair_fish(r, c, fish):
    global position_fishes, board

    board[r][c] = fish
    position_fishes[fish] = [r, c]


def dfs(shark, current_sum, state):
    global position_fishes, board, max_sum, dr, dc

    shark_r, shark_c = shark
    shark_d = int(state[4*shark_r+shark_c])
    eaten_fish = eat_fish(shark_r, shark_c)

    # 상어 움직이기 전에 물고기 먼저 이동
    moved_state = move_fishes(shark_r, shark_c, 0, state)

    can_eat = False
    for i in range(1, 4):
        there_r, there_c = shark_r + dr[0][shark_d] * i, shark_c + dc[0][shark_d] * i

        # 이동할 칸에 물고기가 있으면 잡아먹으러 이동
        if 0 <= there_r < 4 and 0 <= there_c < 4 and board[there_r][there_c] > 0:
            can_eat = True
            there_fish = board[there_r][there_c]
            dfs((there_r, there_c), current_sum + there_fish, moved_state)

    # 잡아먹을 물고기 없으면 지금까지 먹은 물고기 합 저장하고 집에 가기
    if not can_eat:
        max_sum = max(max_sum, current_sum)

    # 물고기 되돌리기
    move_fishes(shark_r, shark_c, 1, moved_state)
    repair_fish(shark_r, shark_c, eaten_fish)


def play_game(start):
    global position_fishes, board

    current_sum = board[0][0]
    dfs((0, 0), current_sum, start)


if __name__ == '__main__':
    direction = [*'012345678']
    dr, dc = [[0,-1,-1,0,1,1,1,0,-1],[0,1,1,0,-1,-1,-1,0,1]], [[0,0,-1,-1,-1,0,1,1,1],[0,0,1,1,1,0,-1,-1,-1]]
    position_fishes = [[] for _ in range(17)]   # [r, c] 저장
    board = [[0 for _ in range(4)] for _ in range(4)]   # 0이면 빈칸, 1~16이면 해당 번호 물고기
    start_state = ''

    max_sum = 0

    for i in range(4):
        tmp = list(map(int, input().split()))
        for j in range(4):
            position_fishes[tmp[2 * j]] = [i, j]
            board[i][j] = tmp[2*j]
            start_state += direction[tmp[2*j + 1]]

    play_game(start_state)
    print(max_sum)