[코딩테스트][백준] 🔥 백준 23290번 "마법사 상어와 복제" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 1시간 10분

import sys
import copy

input=sys.stdin.readline

M,S=map(int,input().split())

dx=[0,0,-1,-1,-1,0,1,1,1]
dy=[0,-1,-1,0,1,1,1,0,-1]

shark_dir={0:(0,0),1:(-1,0),2:(0,-1),3:(1,0),4:(0,1)}

board=[[[] for _ in range(4+1)] for _ in range(4+1)]
smells=[[0]*5 for _ in range(5)]

for i in range(M):
    fx,fy,d=map(int,input().split())
    board[fx][fy].append(d)

sx,sy=map(int,input().split())

def moveFishes(board):
    global smells
    newBoard=[[[] for _ in range(4+1)] for _ in range(4+1)]

    for i in range(1,5):
        for j in range(1,5):
            for fd in board[i][j]:
                nd=fd
                while True:
                    nx=i+dx[nd]
                    ny=j+dy[nd]
                    if nx<1 or ny<1 or nx>=5 or ny>=5:
                        nd=((nd-1)-1)%8+1
                        if nd==fd:
                            newBoard[i][j].append(fd)
                            break
                        continue
                    if smells[nx][ny]>0:
                        nd=((nd-1)-1)%8+1
                        if nd==fd:
                            newBoard[i][j].append(fd)
                            break
                        continue
                    if sx==nx and sy==ny:
                        nd=((nd-1)-1)%8+1
                        if nd==fd:
                            newBoard[i][j].append(fd)
                            break
                        continue
                    newBoard[nx][ny].append(nd)
                    break
    
    return newBoard

def dfs(deep,x,y,method,sum,newBoard):
    global allMethods
    if deep==3:
        allMethods.append((sum,method))
        return
    for i in range(1,5):
        nx=x+shark_dir[i][0]
        ny=y+shark_dir[i][1]
        if nx<1 or ny<1 or nx>=5 or ny>=5:
            continue
        tmp=len(newBoard[nx][ny])
        tmpCopy=newBoard[nx][ny]
        newBoard[nx][ny]=[]
        dfs(deep+1,nx,ny,method+str(i),sum+tmp,newBoard)
        newBoard[nx][ny]=tmpCopy
        

def findMethods():
    global sx,sy
    x,y=sx,sy
    newBoard=copy.deepcopy(board)
    dfs(0,x,y,"",0,newBoard)

for k in range(S):
    allMethods=[]
    copy_board=copy.deepcopy(board)

    board=moveFishes(board)
    
    findMethods()

    allMethods.sort(key=lambda x:(-x[0],x[1]))
    thisMethod=allMethods[0][1]
    for d in thisMethod:
        nx=sx+shark_dir[int(d)][0]
        ny=sy+shark_dir[int(d)][1]
        if len(board[nx][ny])>0:
            smells[nx][ny]=3
            board[nx][ny]=[]
        sx,sy=nx,ny

    for i in range(1,5):
        for j in range(1,5):
            if smells[i][j]>0:
                smells[i][j]-=1

    for i in range(1,5):
        for j in range(1,5):
            board[i][j]+=copy_board[i][j]

answer=0
for i in range(1,5):
    for j in range(1,5):
        answer+=len(board[i][j])
print(answer)

상어의 복제 마법: 물고기를 지켜라! 🦈✨

상어가 복제 마법을 사용하는 과정을 시뮬레이션 하는 문제이다. 시뮬레이션 문제의 특성상 단계를 나눠서 생각하는 것이 편리하다.

먼저 복제 마법을 위해 따로 물고기를 복사해 놓는다. 이 때는 깊은 복사를 사용해 놓아야 한다. 그 다음, 모든 물고기의 이동을 따져야 한다. 이 때, 상어의 위치, 냄새의 배열, 격자의 범위 내를 확인하고 이동시키면 된다.

그 다음 상어의 이동 루트를 확인해야 한다. 이 때, 루트 중, 특정 기준에 따라 루트가 선택되므로 정렬을 사용할 것을 생각해 둔다. DFS로 모든 루트를 탐색하면서 기준에 해당하는 제외되는 물고기 수, 방향의 사전 순 등을 기록해 둔다. 이 때, 후에 냄새가 기록될 것도 염두하고 있어야 한다. 상어의 이동 루트를 이 기준을 통해 정렬해서 찾는다. 그 후, 기록해 둔 이동 방향의 순서, 즉, 문제에서는 방향의 사전 순을 다시 분리해서 읽어드려서 상어의 위치를 갱신하고 물고기가 제외되는 칸에 냄새를 남긴다.

이제 물고기 냄새를 -1씩 해주거나 0으로 만들면 된다. 그리고 복사해 두었던 배열을 다시 사용하던 배열에 이어붙여 복사 마법을 완료시켜 주면 된다.

이렇게 Python으로 백준의 "마법사 상어와 복제" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊