백준 23290번 마법사 상어와 복제 | python | 고전 + 백트래킹

문제

링크

풀이

구현 순서

1. 복제 마법을 진행한다. 결과 자체는 나중에 반영된다.
2. 모든 물고기가 이동한다
   • 못 가는 경우 : 가려는 좌표에 상어가 있거나 물고기 냄새가 있거나 격자 범위가 나감
   • 갈 수 있을 때까지 자신의 방향을 45도 반시계 회전시킨다
   • 그래도 없으면 이동하지 않는다 -> 방향 원래대로 돌려두어야 함
3. 상어가 연속 3칸 이동한다

• 못 가는 경우 : 3칸을 채 이동하지 않았는데 격자를 벗어나는 경우
• 이동경로는 물고기를 가장 많이 제외시킬 수 있는 경로로 선택한다.
  • 가능한 이동경로가 여러가지인 경우 사전순(상 좌 하 우)으로 선택
• 이동 경로에 물고기가 있다면 해당 물고기는 제외되며 해당 칸에 물고기 냄새를 남긴다

4. 2번 전 물고기 냄새가 격자에서 사라진다
5. 1에서의 복제 마법을 실제로 시전한다

사용한 배열

graph : 현재 물고기들의 위치 정보를 담은 2차원배열. 값 자체는 배열을 저장 (4x4)
shark : 상어(y,x) 현재 좌표
smell : 물고기 냄새 저장해두는 칸 (4x4)

• 2차원 그래프 각 칸은 또 리스트로 구성됨 (물고기는 한 칸에 여러 마리 존재할 수 있기 때문)

짚어야할 부분

1. 물고기 관리
   • 물고기를 이동 및 관리 하기 위해 격자 안에 리스트를 두어 각 물고기의 방향값을 append한다. (꼭 리스트로 관리. 물고기는 한 칸에 여러 마리 존재할 수 있기 때문 22)
   • 물고기 실제 이동 자체는 이동방향을 모두 파악하고 나서 그 이후에 모든 물고기가 한 번에 업데이트되어야한다. 중간에 물고기가 이동하던 중에 이전의 물고기들을 이미 업데이트 시켜두는 고전적인 실수는 절대 하지 말자 !
   • 데크 말고 리스트에서도 pop() 잘 활용하기. 나중에 인덱스로 없애고 하는 것보다 실수 가능성 적어보임
2. bfs 백트래킹
   • 사전순 우선순위 설명글을 보면 알 수 있는데 상어가 갈 수 있는 경로는 총 4 x 4 x 4 = 64가지 즉 dfs 백트래킹으로 풀어야함을 알수 있음
   • 여기서 중요한 건 상하상 <- 과 같이 이미 방문했던 곳을 또 갈 수 있다는 것! 이를 간과하면 일부 테케에서 뻑날 수 있으니 조심
   • 여기서 상어가 3칸 움직인다는 뜻은, 내가 각기 다른 칸을 3칸을 이동했다는게 아니라 움직인 누적거리가 3칸이라고 바르게 해석할 줄 알아야한다.
   • visited 정보를 통해 물고기를 board로부터 없애는 작업 (= 빈리스트를 초기화하는 작업)을 꼭 진행해야 함
3. smell 정보
   • smell에 대한 배열 따로 두어서 턴마다 업데이트 및 초기화 잘 해주기
4. copy.deepcopy
   • 가장 처음에 복제 기능을 구현하기 위해 deepcopy로 graph 배열 미리 스냅샷 찍어두고 나중에 graph에 extend

전체 코드

https://ryu-e.tistory.com/107 코드를 가져왔습니다

import copy

def move_fish():
    """
    물고기 이동
    1. 상어가 있는 칸, 물고기 냄새 칸, 벗어나는 칸 x
    2. 45도 반시계 회전 후 이동. 이동 못하는 경우 그대로
    :return:
    """
    res = [[[] for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            while temp[x][y]:
                d = temp[x][y].pop()
                for i in range(d, d - 8, -1):
                    i %= 8
                    nx, ny = x + f_dx[i], y + f_dy[i]
                    if (nx, ny) != shark and 0 <= nx < 4 and 0 <= ny < 4 and not smell[nx][ny]:
                        res[nx][ny].append(i)
                        break
                else:
                    res[x][y].append(d)
    return res

def dfs(x, y, dep, cnt, visit):
    """
    상어 3칸 이동
    1. 제외되는 물고기 수가 많고 > 이동방법 사전순(백트래킹하면 자동으로 됨)
    2. 이동한 곳을 저장 > 물고기 냄새가 됨
    """
    global max_eat, shark, eat
    if dep == 3:   # 3번 이동한 경우 그만
        if max_eat < cnt:
            max_eat = cnt
            shark = (x, y)
            eat = visit[:]
        return
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < 4 and 0 <= ny < 4:
            if (nx, ny) not in visit:  # 처음 방문, cnt에 죽은 물고기 수 추가
                visit.append((nx, ny))
                dfs(nx, ny, dep + 1, cnt + len(temp[nx][ny]), visit)
                visit.pop()
            else:  # 방문한 경우
                dfs(nx, ny, dep + 1, cnt, visit)

#       ←, ↖,   ↑,  ↗, →, ↘, ↓, ↙
f_dx = [0, -1, -1, -1, 0, 1, 1, 1]
f_dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

m, s = map(int, input().split())
fish = [list(map(int, input().split())) for _ in range(m)]
graph = [[[] for _ in range(4)] for _ in range(4)]

for x, y, d in fish:
    graph[x - 1][y - 1].append(d - 1)

shark = tuple(map(lambda x: int(x) - 1, input().split()))
smell = [[0] * 4 for _ in range(4)]

for _ in range(s):
    eat = list()
    max_eat = -1
    # 1. 모든 물고기 복제
    temp = copy.deepcopy(graph)
    # 2. 물고기 이동
    temp = move_fish()
    # 3. 상어이동 - 백트래킹
    dfs(shark[0], shark[1],0, 0, list())
    for x, y in eat:
        if temp[x][y]:
            temp[x][y] = []
            smell[x][y] = 3   # 3번 돌아야 없어짐
    # 4. 냄새 사라짐
    for i in range(4):
        for j in range(4):
            if smell[i][j]:
                smell[i][j] -= 1
    # 5. 복제 마법
    for i in range(4):
        for j in range(4):
            graph[i][j] += temp[i][j]

# 물고기 수 구하기
answer = 0
for i in range(4):
    for j in range(4):
        answer += len(graph[i][j])

print(answer)