[백준] 19236번 - 청소년 상어 (파이썬)

https://www.acmicpc.net/problem/19236

 

# 청소년 상어
import copy
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 0, -1, -1, -1, 0, 1, 1, 1]
arr = []
fish = [[0]]
for k in range(4):
    temp = list(map(int, input().split()))
    arr.append([temp[i] for i in range(0, len(temp), 2)])
    for i in range(0, len(temp), 2):
        fish.append([temp[i], [k, i//2, temp[i+1]]])


def fish_move(arr, fish):
    for i, temp in enumerate(fish):
        if i != 0:
            x, info = temp
            if not eat[x]:
                x, y, dir = info
                while True:
                    nx = x + dx[dir]
                    ny = y + dy[dir]
                    if 0 <= nx < 4 and 0 <= ny < 4 and arr[nx][ny] != 'shark':
                        if arr[nx][ny] == 0:
                            temp = arr[x][y]
                            fish[temp][1][0], fish[temp][1][1] = nx, ny
                            arr[nx][ny] = arr[x][y]
                            arr[x][y] = 0
                        else:
                            change_fish(arr, fish, x, y, nx, ny)
                        break
                    else:
                        dir = change_dir(dir)
                        fish[i][1][2] = dir


def change_fish(arr, fish, x, y, nx, ny):
    fish[arr[x][y]][1][0] = nx
    fish[arr[x][y]][1][1] = ny
    fish[arr[nx][ny]][1][0] = x
    fish[arr[nx][ny]][1][1] = y
    temp = arr[x][y]
    arr[x][y] = arr[nx][ny]
    arr[nx][ny] = temp


def change_dir(dir):
    ndir = dir + 1
    if ndir == 9:
        ndir = 1
    return ndir


def shark_eat_dfs(arr, fish, now, cnt):
    global result
    temp = copy.deepcopy(arr)
    fish_temp = copy.deepcopy(fish)
    fish_move(temp, fish_temp)
    can_eat_list = shark_can_eat(temp, fish_temp, now)
    for x in can_eat_list:
        if temp[x[0]][x[1]] != 0:
            t = temp[x[0]][x[1]]
            eat[temp[x[0]][x[1]]] = True
            temp[x[0]][x[1]] = 'shark'
            temp[now[0]][now[1]] = 0
            shark_eat_dfs(temp, fish_temp, x, cnt+t)
            temp[x[0]][x[1]] = t
            temp[now[0]][now[1]] = 'shark'
            eat[temp[x[0]][x[1]]] = False
    result = max(result, cnt)


def shark_can_eat(arr, fish, t):
    temp = []
    x, y, dir = t[0], t[1], t[2]
    nx, ny = x+dx[dir], y+dy[dir]
    while 0 <= nx < 4 and 0 <= ny < 4:
        if arr[nx][ny] != 0:
            temp.append(fish[arr[nx][ny]][1])
        nx += dx[dir]
        ny += dy[dir]
    return temp


fish.sort()
eat = [False] * 17
eating = arr[0][0]
arr[0][0] = 'shark'
eat[eating] = True

result = 0
shark_eat_dfs(arr, fish, fish[eating][1], fish[eating][0])
print(result)

 

구현, 백트랙킹
1. arr을 입력을 받는다 (물고기 숫자만) : 4x4격자 내부의 특정 물고기 숫자 위치
2. fish를 입력을 받는다 ([물고기 숫자, [x좌표, y좌표, dir]]) 이후, 정렬
3. 시작하기 전에 상어의 위치를 0,0에 위치시키고 eat리스트로 방문처리
4. shark_eat_dfs : 상어가 먹을 수 있는 모든 경우의 수 탐색
    - fish_move : 물고기의 번호가 작은 순서대로 문제의 조건에 맞게 이동
        - change_fish : 물고기 자리 교체
        - change_dir : 방향 변경
    - shark_can_eat : 상어가 먹을 수 있는 물고기 리스트를 반환
    - 상어가 먹을 수 있는 물고기 리스트마다 각각 다시 shark_eat_dfs 실행
    - result 값 초기화
5. result 출력

 

보기만 해도 머리 아픈 삼성 SW기출 구현(시뮬레이션) 문제이다

사실 며칠 전부터 풀려고 했는데 코로나 때문에 컨디션이 안 좋아서 미뤄왔었다.

그래도 나름 원트에 클리어했다.

copy의 deepcopy(깊은 복사)를 사용해서 dfs가 끝나고 돌아와서

다른 경우의 수를 실행할 때, 영향을 받지 않도록 해야 한다.

 

이전에 풀었던 문제와 이어지는 스토리가 있는 문제이다.

[백준] 16236번 - 아기 상어

[백준] 16236번 - 아기 상어 (파이썬)