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

백준 19236 - 청소년 상어

시간 제한 1초(추가 시간 없음), 메모리 제한 512MB

# 조건

• 아기 상어가 성장해 청소년 상어가 되었다.
• 4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다.
• 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다.
• 한 칸에는 물고기가 한 마리 존재한다.
• 각 물고기는 번호와 방향을 가지고 있다.
  • 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다.
  • 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
• 오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다.
• 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다.
• 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다.
  • 이후 물고기가 이동한다.
• 물고기는 번호가 작은 물고기부터 순서대로 이동한다.
• 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.
• 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
  • 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.
  • 그 외의 경우에는 그 칸으로 이동을 한다.
• 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
• 물고기의 이동이 모두 끝나면 상어가 이동한다.
• 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다.
• 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.
• 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.
• 물고기가 없는 칸으로는 이동할 수 없다.
• 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.
• 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

• <그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다.
• 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다.
• <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

• 이제 물고기가 이동해야 한다.
• 1번 물고기의 방향은 ↗이다.
• ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다.
• 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다.
  • 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

• 2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다.
• 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다.
• 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

• 3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다.
• 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다.
  • ← 방향에는 상어가 있으니 또 회전을 해야 한다.
  • ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다.
• 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

• 물고기가 모두 이동했으니 이제 상어가 이동할 순서이다.
• 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다.
• 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

• 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

• 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다.
• 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다.
• 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

• 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

# 접근 방법

• 문제 설명이 길어 이해하는데 시간이 걸렸다.
• 요약하자면, 각 물고기의 이동은 상어와 좌표 바깥이 아닌 이상 서로의 위치를 교환하는 형식이다.
• 작은 번호의 물고기부터 이동이 끝난 후 상어가 이동을 하는데
  • 현재 가지고 있는 방향 중 원하는 곳으로 갈 수 있다.
  • 이 때, 먹을 수 있는 물고기가 없으면 탐색이 끝나게 되는 것이고
  • 탐색이 끝났을 때, 먹었던 물고기 번호의 합이 최대가 되면 된다.
• 물고기의 이동은 각 물고기의 위치와 방향을 리스트에 기록해주고, 문제의 조건대로 이동시키면 된다.
  • 주의할 점은, 갈 수 있는 곳이 없다면 제자리에서 오른쪽으로 45도 회전한 결과를 반환해야 되는 것이다.
• 상어의 경우 현재 진행 방향에 놓인 물고기 중 어떤 고기를 먹느냐에 따라 결과가 달라지므로 백트래킹을 이용하여 경우의 수를 탐색해주면 된다.

상세 로직

• 입력받은 물고기의 정보 중 물고기 번호는 arr 2차원 리스트에 담아주고, 번호와 방향은 fishes 리스트에 담아준다.
• 0, 0의 물고기는 상어한테 먹히고 시작하므로 shark의 시작은 fishes[arr[0][0]]으로 초기화 해준다.
• dfs(arr, cnt, fishes) 를 넣어주는데 현재 물고기 번호의 상태 배열, 현재까지 누적 물고기 번호의 합, 물고기들의 상태이다.
  • dfs를 시작하면서 deepcopy를 사용하여 arr과 fishes의 원본 배열을 복사해준다.
  • 상어가 물고기를 먹고 시작하였으므로 복사한 temp를 move함수에 넣어주며 물고기를 이동시킨다.
• 이동이 완료되었다면, 상어가 이동 가능한 방향으로 이동하며 좌표를 벗어난다면 cnt를 result와 비교 후 return 해준다.
  • 물고기가 없다면 continue
• 이동할 칸의 물고기 번호와 정보, 현재 상어의 위치를 기록해주고
  • 현재 이동할 칸을 0으로 빈칸, 상어의 다음 위치를 변경해준다.
• 더 이상 먹을 수 없어서 이전의 값으로 돌아왔다면 미리 저장해둔 정보로 다시 복구 시켜준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from copy import deepcopy  

def dfs(new_arr, cnt, new_fish):  
    global result, shark  
    temp_arr = deepcopy(new_arr)  
    temp_fish = deepcopy(new_fish)  
    move(temp_arr, temp_fish)  
    ni, nj, nd = shark  
    while True:  
        ni, nj = ni + di[nd], nj + dj[nd]  
        if not 0<=ni<4 or not 0<=nj<4:     # 좌표를 벗어난다면 return  
            result = max(result, cnt)  
            return  
        if not temp_arr[ni][nj]:           # 물고기가 없다면 다음 좌표  
            continue  

        val = temp_arr[ni][nj]              # 상어가 이동할 칸의 물고기 번호  
        info = temp_fish[val]               # 물고기 정보  
        temp_arr[ni][nj] = -1               # 상어로 변경  
        temp_arr[shark[0]][shark[1]] = 0    # 상어가 있던 칸은 빈칸으로 변경  
        temp_shark = shark                  # 직전 상어가 있던 곳 기록  
        temp_fish[val] = []                 # 먹은 물고기 초기화  
        shark = [ni, nj, info[2]]           # 상어 정보 업데이트  
        dfs(temp_arr, cnt + val, temp_fish)  
        temp_fish[val] = info                # 재귀 돌리기 전 변경한 정보 복구하기  
        shark = temp_shark  
        temp_arr[ni][nj] = val  
        temp_arr[shark[0]][shark[1]] = -1  

def move(new_arr, new_fish):  
    for i in range(1, 17):  
        if new_fish[i]:  
            si, sj, nd = new_fish[i]  
            for d in range(8):  
                ni, nj = si+di[(nd+d) % 8], sj + dj[(nd+d) % 8]  
                # 좌표 내이고 상어가 아니면 교환해주기  
                if 0<=ni<4 and 0<=nj<4 and new_arr[ni][nj] != -1:  
                    # 교환 할 자리에 다른 물고기가 있다면  
                    # 현재 위치 + 기존 방향으로 기록                    
                    new_arr[ni][nj], new_arr[si][sj] = new_arr[si][sj], new_arr[ni][nj]  
                    if new_fish[new_arr[si][sj]]:  
                        new_fish[new_arr[si][sj]] = [si, sj, new_fish[new_arr[si][sj]][2]]  
                    new_fish[i] = [ni, nj, (nd+d) % 8]  
                    break  
            else:  
                # 갈 수 있는 곳이 없다면 방향 오른쪽 45도로 변경  
                new_fish[i] = [si, sj, (nd+7) % 8]  


# 위 좌상 좌 좌하 하 우하 우 우상  
di, dj = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]  

# 물고기 번호를 인덱스로 => 위치와 방향 기록  
fishes = [[] for _ in range(17)]  
# 좌표에 물고기 번호 기록  
arr = [[0] * 4 for _ in range(4)]  
for si in range(4):  
    info = [*map(int, input().split())]  
    # 위치와 방향으로 기록해주기  
    for sj in range(0, 8, 2):  
        fishes[info[sj]] = [si, sj//2, info[sj+1]-1]  
        arr[si][sj//2] = info[sj]  

result = 0  
# 물고기 번호 기록한 배열, cnt, 물고기 정보  
# 0, 0의 물고기는 다시 복구 해줄 필요없음  
# 없애주고 정보 상어로 변경해주기  
val = arr[0][0]  
shark = fishes[val]  
fishes[val] = []  
arr[0][0] = -1  

dfs(arr, val, fishes)  
print(result)

• 확실히 구현, 시뮬레이션 문제는 처음에 아이디어와 의사 코드를 작성할 때 세부적으로 작성하는 것이 중요한 것 같다.
• 함수도 세부적으로 모듈화하는 것이 디버깅하는 것에도 많은 도움이 되기 때문에, 범위 체크 같은 것도 나눠서 하는 연습을 하면 좋을 것 같다..!