[Python] 백준 23290 마법사 상어와 복제

1. 문제 링크

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

23290번: 마법사 상어와 복제

2. 문제 요약

1. 모든 물고기 복제 

2. 물고기 이동 

• 상어가 있는 칸, 물고기 냄새 칸, 벗어나는 칸 x
• 45도 반시계 회전 후 이동. 이동 못하는 경우 그대로

3. 상어 이동 

• 제외되는 물고기 수가 많고 > 이동 방법 사전 순 이동하게 됨
• 상어가 이동한 곳은 물고기가 있으면 물고기 냄새가 생김

4. 2번 전 물고기 냄새 사라짐

5. 복제 마법 

3. 아이디어 정리

1. 모든 물고기 복제 ⇒ 물고기 위치 복제 (copy)

2. 물고기 이동 ⇒ 구현 move_fish()

• 상어가 있는 칸, 물고기 냄새 칸, 벗어나는 칸 x
• 45도 반시계 회전 후 이동. 이동 못하는 경우 그대로

3. 상어 이동 ⇒ 백트래킹 dfs

• 제외되는 물고기 수가 많고 > 이동 방법 사전 순 이동하게 됨
• 상어가 이동한 곳은 물고기가 있으면 물고기 냄새가 생김

4. 2번 전 물고기 냄새 사라짐 ⇒ 냄새 -1

5. 복제 마법 ⇒ 기존 물고기 + 복제된 물고기 추가

 

4. 문제 풀이

4-1. 내 풀이

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)

 

 

5. 결론

• 구현
• 백트래킹

참고 사이트

• https://yabmoons.tistory.com/719
• https://devlibrary00108.tistory.com/m/662