백준 23290번 마법사 상어와 복제 (Python)

물고기가 돌아다니고 있는 4*4 크기의 격자에 마법사 상어가 돌아다니며 마법 연습을 할 경우 마지막에 격자에 남아있는 물고기의 숫자를 구하는 문제입니다.

마법 연습의 순서는 다음과 같습니다.

1. 상어가 모든 물고기에게 복제 마법을 시전합니다. 복제 마법은 시간이 오래걸리기 때문에 5번째 순서에서 물고기 복제가 완료됩니다.

 

2. 모든 물고기에게는 처음에 주어진 방향이 있습니다. 이 방향대로 움직이는데, 해당 방향으로 움직일 수 없을 경우 반시계 방향으로 45도 회전한 다음 다시 이동을 시도합니다. 만약, 이동할 수 있는 칸이 없다면 이동하지 않습니다.

물고기가 이동할 수 없는 칸은 다음과 같습니다.

• 상어가 있는 칸
• 물고기의 냄새가 있는 칸
• 격자의 범위를 넘어가는 칸

 

3. 상어는 무조건 연속해서 3칸 움직입니다. 상어는 상하좌우로 움직일 수 있고 격자 범위를 넘어서지 않는다면 모든 칸을 이동할 수 있습니다.

상어의 이동 조건은 다음과 같습니다.

• 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법입니다.
• 가능한 이동 방법 중, 이동하는 칸에 있는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용합니다. (사전순은 아래 정의)
• 상어가 이동하는 칸의 물고기는 모두 제거됩니다. (물고기가 제거된 모든 칸은 물고기의 냄새가 남습니다.)

4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라집니다.

5. 1.에서 사용한 복제 마법이 완료됩니다. 모든 복제된 물고기는 1에서의 위치와 방향이 모두 같습니다.

 

입력으로 주어지는 물고기의 방향은 1~8로 주어지며 각각 좌, 좌상, 상, 우상, 우, 우하, 하, 좌하 입니다.

상어의 이동 방법 중 사전 순이란

• 상은 1, 좌는 2, 하는 3, 우는 4로 변환합니다.
• 상하좌, 하우하로 이동할 경우 변환된 숫자는 132, 343입니다. 132<343이므로 상하좌는 하우하보다 사전순에서 앞선 것입니다.

 

위의 조건을 읽고나서 여러 조건들이 헷깔렸고 이를 정리해두고 문제를 풀이했습니다.

• 상어는 이동 시, "상우좌"처럼 이동한 장소를 두 번 갈 수 있습니다.
• 물고기 이동 시 물고기 냄새에 대한 조건이 물고기를 이동시키지 못 할 수 있습니다. 각 턴에서 물고기 냄새가 없어지는 순서보다 물고기 이동이 먼저 이기 때문에, 만약 2번째 연습에서 생긴 물고기 냄새는 4번째 연습 때 물고기 이동 시 반영되고, 5번째 연습 때는 물고기 이동 시 반영되지 않습니다.
• 격자는 1,1이 가장 왼쪽 위칸이고 4,4가 가장 오른쪽 아래칸이므로 이를 염두해야합니다. 물고기의 방향도 1~8로 0부터 시작하지 않음을 조심해야합니다.

 

풀이

각 순서대로 차근차근 방법을 생각하여 문제를 풀어주었습니다.

미리 예기를 해보자면 상어의 위치를 6*6 격자로 선언해서 모든 칸을 계속 순회하면서 확인하면 시간 초과가 나므로 defaultdict를 이용해 풀이했습니다.

 

0.변수 선언

M,S=list(map(int,input().split()))
fishList=[list(map(int,input().split())) for _ in range(M)]
wizard = list(map(int,input().split()))
fishDirection = [(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0)]
wizardDirection = [(-1,0),(0,-1),(1,0),(0,1)]
smellMaps = [[-1 for _ in range(6)] for __ in range(6)] # -1 빈곳, 양수: 물고기냄새 사라지는 턴
wizardMaps = [[-1 for _ in range(6)] for __ in range(6)] # -1 빈곳, -2:위자드
visited=[[False for _ in range(6)] for __ in range(6)]
fishMaps = defaultdict(list)

wizardMaps[wizard[0]][wizard[1]]=-2

for fx,fy,d in fishList:
    fishMaps[(fx,fy)].append(d%8)

• fishDirection은 물고기가 움직이는 방향이 저장되어 있습니다. 주어진 물고기 방향은 1~8로 시작하므로 저와 같은 경우 8번째 방향을 인덱스 0에 넣어줌으로써 (주어진 방향)%8을 통해 방향을 정할 때 수월하게 할 수 있도록 했습니다.
• wizardDirection은 마법사가 이동하는 방향의 사전 순 입니다.
• smellMaps는 물고기의 냄새가 남아있는 칸을 저장합니다. 양수일 경우 물고기냄새가 사라지는 턴입니다. 만약 smellMaps[i][j]=2일 경우 2번째 턴 물고기 이동까지 영향을 미치게 됩니다.
• wizardMaps는 마법사의 위치를 저장합니다. (딱히 필요없는 것 같습니다.)
• visited는 마법사가 움직일 경우 사용합니다.
• fishMaps는 좌표에 위치한 물고기를 저장하는 dictionary입니다. 입력받은 물고기를 통해 초기화해줍니다.

 

1. 상어 복제 마법

for turn in range(S):
    #1
    copiedMaps=copy.deepcopy(fishMaps)

fishMaps를 깊은 복사로 저장해둡니다. fishMaps의 value들이 모두 리스트이기 때문에 깊은 복사를 해주어야 합니다.

 

2. 물고기 이동

for turn in range(S):
    ...
    #2
    
    newFishMap=defaultdict(list)
    for (i,j),dList in fishMaps.items():
        for od in dList:
            nx,ny,d=0,0,od
            for k in range(8):
                nx,ny=i+fishDirection[d][0],j+fishDirection[d][1]
                
                if not (1<=nx<=4 and 1<=ny<=4) or turn<=smellMaps[nx][ny] or wizardMaps[nx][ny]==-2:
                    d=d-1 if d-1>=0 else 7
                    continue
                newFishMap[(nx,ny)].append(d)
                break        
            else:
                newFishMap[(i,j)].append(od)
                continue
            
    fishMaps=copy.deepcopy(newFishMap)

새롭게 물고기들을 저장할 변수 newFishMap을 선언해줍니다.

fishDirections를 통해 순서대로 방향을 설정해줍니다.

해당 방향으로 이동 가능할 경우 newFishMap에 새로운 위치 키값에 방향을 밸류로 넣어줍니다.

해당 방향으로 이동 불가능할 경우 newFishMap에 기존 위치 키값에 방향을 밸류로 넣어줍니다.

다시 fishMaps에 저장해줍니다.

 

3. 마법사 이동

먼저 이동하려는 경로를 구하는 재귀 함수를 구해보도록 하겠습니다.

def move(x,y,count,fishCount,path):
    global maxFishCount,maxPath
    if count==3:
        if maxFishCount<fishCount:
            maxPath=path[:]
            maxFishCount=fishCount
        return
            
    for i in range(4):
        nx,ny=x+wizardDirection[i][0],y+wizardDirection[i][1]
        
        if not (1<=nx<=4 and 1<=ny<=4):
            continue
        
        newPath=path[:]
        newPath.append((wizardDirection[i][0],wizardDirection[i][1]))
        
        if visited[nx][ny]:
            move(nx,ny,count+1,fishCount,newPath)
        else:
            visited[nx][ny]=True
            move(nx,ny,count+1,fishCount+len(fishMaps[(nx,ny)]),newPath)
            visited[nx][ny]=False

3번 움직였을 경우 현재까지의 최대 물고기 수와 현재 물고기 수를 비교해줍니다. 현재 물고기 수가 더 크다면 현재 경로와 최대 물고기 수를 교체해줍니다.

상, 좌, 하, 우 사전 순서대로 탐색을 하게 해서, 만약 상상좌와 좌좌좌 이동 경로에 같은 수의 물고기수가 있다고 해도 상상좌의 경로를 먼저 탐색하므로 사전 순이 앞선 것이 먼저 저장이 되게 했습니다.

다음 탐색할 좌표가 이 번 3번의 움직임 동안 먼저 방문한 곳이라면, fishCount는 증가시키지 않고 이동시켜줍니다.

먼저 방문하지 않은 곳이라면, 해당 좌표의 visited를 True로 변경해주고 해당 좌표의 물고기 수만큼 fishCount도 증가해주고 이동합니다.

 

for turn in range(S):
    ...
    #3
    maxPath=[]
    maxFishCount=-1
    move(wizard[0],wizard[1],0,0,[])
    
    nx,ny=wizard
    wizardMaps[nx][ny]=-1
    for dx,dy in maxPath:
        nx+=dx
        ny+=dy
        if len(fishMaps[(nx,ny)])>0:
            smellMaps[nx][ny]=turn+2
            fishMaps[(nx,ny)].clear()
    wizard[0],wizard[1]=nx,ny
    wizardMaps[nx][ny]=-2

move를 통해 얻은 최대 물고기를 얻을 수 있는 경로로 마법사를 이동시키면서 해당 경로의 물고기들을 모두 제거해줍니다.

여기서 주의할 점은 마법사 주위에 물고기를 얻을 수 없어도 마법사는 움직인다는 점입니다. 이럴 경우 움직일 수 있는 경로 중 사전 순이 빠른 경로로 이동하게 됩니다. (maxFishCount 초기값을 -1로 설정하여 구현했습니다.)

 

이동 경로의 물고기가 존재할 경우 smellMaps의 해당 좌표에 turn+2를 저장해줍니다. 이 값을 통해 물고기는 몇 번째 turn에 해당 좌표로 이동 가능한지 알 수 있습니다.

이동 경로에 존재하는 물고기는 모두 제거해줍니다.

 

4. 물고기 냄새

물고기 냄새는 위의 smellMaps를 통해 구현했습니다. 물고기 이동 시 smellMaps[i][j]의 값과 현재 turn을 비교하여 이동 가능 여부를 알 수 있습니다.

 

5. 물고기 복제 완료

for turn in range(S):
    ...
    for pos,dList in copiedMaps.items():
        fishMaps[pos].extend(dList)

복제했던 물고기들을 다시 fishMaps에 넣어줍니다.

 

6. 출력

answer=0
for pos,dList in fishMaps.items():
    answer+=len(dList)
print(answer)

각 격자에 남아있느 물고기를 출력해줍니다.

 

 

 

이번 문제는 문제 설명을 읽고 어떤 자료구조가 어울릴지, 시간 초과를 줄이려면 어떻게 해야하는지 생각을 계속해줘야 하는 문제여서 오래걸리게 되었습니다. 특히 문제를 읽고 딸려오는 조건들을 생각해내는 것이 조금 어려웠습니다(물고기와 상어가 같은 칸에 존재할 때 상어가 움직이면 처음 상어가 있던 칸의 물고기도 먹는지, 상어 주변에 물고기가 없을 경우 이동가능한 경로 중 사전 순이 빠른 경로로 움직인다). 이를 빠르게 유추하는 것도 중요하다는 것을 느꼈습니다.