Baekjoon 19236. 청소년 상어 / Python

19236. 청소년 상어

난이도 : 골드 2
소요 시간 : 35분
날짜 : 2024.12.27
언어 : 파이썬
알고리즘 유형 : 백트래킹, 구현, 시뮬레이션

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 상어 이동, 물고기 이동 을 반복함.
2. 상어 이동
   • 경계 안에서만 이동
   • 물고기가 있는 곳으로만 이동
   • 여러 칸 이동 가능
   • 물고기의 방향을 흡수?함
   • 이동 불가 : 집으로 감
3. 물고기 이동
   • 번호 작은 물고기부터 순서대로 이동
   • 경계 안에서만 이동
   • 한 칸만 이동
   • 상어 있는 곳으로 이동 불가
   • 다른 물고기가 있다면 자리 교체
   • 이동 불가 : 이동 안함
4. "잡아먹은 물고기 번호의 합"의 최댓값을 구하라.

2. 해결 방식

dfs + 백트래킹

1. 상어 이동
   • 방향에 맞게 이동시키고 해당 자리의 물고기를 배열에서 없앤다.
   • 이동할 때마다 res를 max 값으로 갱신했다.
2. 물고기 이동
   • 각 번호의 물고기의 이동 가능한 방향을 찾는다. : 없으면 continue
   • 그 곳에 물고기 없으면 이동, 갱신하기
   • 물고기 있으면 이동 후 두 곳을 갱신한다.

:여러 백트래킹 조건을 사용해야 하고, 조금 복잡하지만, 구현의 어려움은 없던 문제 같다.

3. 정답 코드

import sys;input = sys.stdin.readline
from copy import deepcopy

Fields = [[0] * 4 for _ in range(4)]    # Fields[i][j] = i, j에 있는 물고기 번호, 없으면 0, 상어면 -1
direction = [
    (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)
]
res = 0

def input_data():
    for x in range(4):
        line  = list(map(int, input().split()))
        for y in range(4):
            index, d = line[y * 2], line[y * 2 + 1] - 1
            Fields[x][y] = [index, d]

def dfs(x_s=0, y_s=0, ans=0, fields=Fields):
    global res
    ans += fields[x_s][y_s][0]
    d_s = fields[x_s][y_s][1]
    fields[x_s][y_s] = [-1, d_s]
    res = max(ans, res)

    # 물고기 이동
    for index_f in range(1, 17):
        # 위치 초기화 
        x_f, y_f = -1, -1
        # 위치 및 방향 정해주기
        for check_f in range(0, 16):
            if index_f == fields[check_f // 4][check_f % 4][0]:
                x_f, y_f = check_f // 4, check_f % 4
                break
        d_f = fields[x_f][y_f][1]
        # 방향이나 위치 어긋나면 skip
        if d_f == -1:continue
        if x_f == -1 or y_f == -1:continue
        # 이동 가능 방향 찾기
        can_move = False
        for _ in range(8):
            nx_f, ny_f = x_f + direction[d_f][0], y_f + direction[d_f][1]
            if 0 <= nx_f < 4 and 0 <= ny_f < 4 and (nx_f, ny_f) != (x_s, y_s):
                can_move = True
                break
            d_f = (d_f + 1) % 8
        if not can_move:continue
        # 움직일 곳에 물고기가 없는 경우와 잇는 경우
        if fields[nx_f][ny_f] == 0:
            fields[x_f][y_f] = [0, -1]
            fields[nx_f][ny_f] = [index_f, d_f]
        else:
            index_other_f, d_other_f = fields[nx_f][ny_f]
            fields[x_f][y_f] = [index_other_f, d_other_f]
            fields[nx_f][ny_f] = [index_f, d_f]

    # 상어 이동
    for power in range(1, 4):   # 최대 3칸 이동
        nx_s, ny_s = x_s + power * direction[d_s][0], y_s + power * direction[d_s][1]
        if nx_s in range(4) and ny_s in range(4):
            if fields[nx_s][ny_s][0] > 0:
                fields[x_s][y_s] = [0, -1]
                dfs(nx_s, ny_s, ans, deepcopy(fields))
                fields[x_s][y_s] = [-1, d_s]

input_data()
dfs()

print(res)