문제

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

나의 코드

"""

"""

from copy import deepcopy

"""
1. 물고기 복제 - deepcopy() 이용
2. 물고기 이동 - 3중 반복문을 이용
3. 상어의 이동 - 백트래킹 이용 (★중요)
4. 물고기 냄새 없애기 - 단순 반복문
5. 물고기 복제해놓은것 더하기 - 단순 반복문
6. 남은 물고기 세기 - 단순 반복문
"""

M, S = map(int, input().split()) # M:물고기의 수, S:마법 횟수
pan = [ [ [] for _ in range(4) ] for _ in range(4) ] # 4 * 4 격자판
fish = [ list(map(int, input().split())) for _ in range(M) ] # 물고기 정보 (x, y, d:방향)
smell_fish = [ [0] * 4 for _ in range(4) ] # 물고기의 냄새 정보 격자판
visited = [ [False] * 4 for _ in range(4) ] # 상어가 이동할 때 백트래킹 사용하기 위한 방문 체크용 배열
s_x, s_y = map(int, input().split()) # 상어의 좌표
s_x, s_y = s_x-1, s_y-1 # 상어의 좌표가 격자판 범위와 1차이 나기 때문에 줄여줌

s_dx = [0, -1, 0, 1, 0] # 상어 이동방향 - 1 ~ 4(상, 좌, 하, 우)
s_dy = [0, 0, -1, 0, 1]
dx = [0, -1, -1, -1, 0, 1, 1, 1] # 물고기 이동방향 - 0 ~ 7(서, 서북, 북, 북동 ~ 남서)
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
for x, y, d in fish: # 물고기의 정보(방향)를 격자판에 기록
    pan[x-1][y-1].append(d-1)

def fish_move(arr): # 물고기의 이동 구현한 함수

    tmp_arr = [ [ [] for _ in range(4) ] for _ in range(4) ]
    for i in range(4):
        for j in range(4):
            while arr[i][j]:
                d = arr[i][j].pop()
                for k in range(d, d-8, -1): # 반시계 방향으로 45도 회전
                    k %= 8
                    mx = i + dx[k]
                    my = j + dy[k]

                    if not (0 <= mx < 4 and 0 <= my < 4): # 격자판 범위를 벗어나면 다음 방향으로 설정
                        continue
                    elif mx == s_x and my == s_y: # 상어가 있다면 다음 방향으로 설정
                        continue
                    elif smell_fish[mx][my] > 0: # 물고기 냄새가 있다면 다음 방향으로 설정
                        continue
                    else:
                        tmp_arr[mx][my].append(k) # 이동방향과 함께 물고기 이동 시키고 break
                        break
                else:
                    tmp_arr[i][j].append(d) # 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. = 그 자리에 머무른다

    return tmp_arr

def shark_move(x, y, dep, shark_eat, visited): # 백트래킹으로 상어 이동 구현 - ★백트래킹을 이용하면 자동적으로 사전순 정렬됨★

    global fish_maxeat, fish_eated, shark_xy

    if dep == 3:
        if fish_maxeat < shark_eat:
            fish_maxeat = shark_eat # 잡아먹힌 물고기의 개수
            fish_eated = visited[:] # 잡아먹힌 물고기의 좌표
            shark_xy = (x, y) # 이동한 상어 좌표 업데이트
        return

    for k in range(1, 4+1):
        mx = x + s_dx[k]
        my = y + s_dy[k]

        if 0 <= mx < 4 and 0 <= my < 4:
            if (mx, my) not in visited:
                visited.append((mx, my))
                shark_move(mx, my, dep+1, shark_eat+len(pan[mx][my]), visited)
                visited.pop()
            else:
                shark_move(mx, my, dep+1, shark_eat, visited)

def smell_out(arr):

    for i in range(4):
        for j in range(4):
            if arr[i][j] > 0:
                arr[i][j] -= 1

    return arr

def fish_copy(copy_arr, arr):

    for i in range(4):
        for j in range(4):
            arr[i][j] += copy_arr[i][j]

    return arr

for s in range(S): # S번 마법을 반복한다.

    # 1. 물고기 정보 복제
    copy_pan = deepcopy(pan)

    # for i in pan:
    #     print(i)
    # print()

    # 2. 물고기의 이동
    pan = fish_move(pan)

    # for i in pan:
    #     print(i)
    # print()

    # 3. 상어의 이동(백트래킹)
    fish_maxeat = -1
    fish_eated = []
    shark_xy = []
    shark_move(s_x, s_y, 0, 0, [])

    # 3-1. 상어한테 잡아먹힌 물고기의 좌표를 이용하여 격자판에서 제외시키기 + 물고기 냄새 남기기
    for x, y in fish_eated:
        while pan[x][y]:
            smell_fish[x][y] = 3
            pan[x][y].pop()

    # 3-2. 이동한 상어의 좌표 업데이트 하기
    s_x, s_y = shark_xy

    # for i in pan:
    #     print(i)
    # print()

    # 4. 물고기 냄새 없애기
    smell_fish = smell_out(smell_fish)

    # 5. 물고기 복제 하기
    pan = fish_copy(copy_pan, pan)


answer = 0
for i in range(4):
    for j in range(4):
        answer += len(pan[i][j])

print(answer)
    

설명

1. fish_move() 부분에 k %= 8 이 부분이 중요한데 좌표 값을 더하기 전에 이 값을 넣어 줘야 한다. 처음에 mx = (i + dx[k]) % 8 이렇게 설정 했는데 이것은 이미 좌표가 더해진 상태에서 하는 것이므로 격자판의 범위를 벗어나느냐 마냐를 구현할 수 있는 것이지 이 문제처럼 반시계 방향으로 계속 돌아야 한다면 좌표 값을 더하기 전에 방향에 [%= 방향횟수] 해줘야 한다.

2. 백트래킹 이용하는 부분은 계속 다시 보기

3. 백트래킹 부분에 visited가 아닌 visited[:]로 해야 배열 전체가 반환이 된다.

4. 물고기 냄새 부분은 True, False가 아닌 애초에 3의 숫자를 넣어 1씩 줄여주면 카운트 처럼 사용 가능해서 쉽게 구현 가능하다.

참고 자료

• 백트래킹 부분 참조함

https://ryu-e.tistory.com/107