[python] BOJ 백준 23290: 마법사 상어와 복제

1. 문제  

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다. 격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

2. 입력   

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.

격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.

3. 출력   

S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.

 

4. 해결방법   

삼성에서 자주 출제되는 시뮬레이션 문제이다. 삼성기출 '어항정리'와 비슷하게 문제에서 제시된 순서에 맞게 코드를 짜면되고, 별다른 로직이나 자료구조를 사용할 필요는 없다. 

1) move 함수: 상어를 움직이는 함수이다. 상어가 이동하면서 최대한 많은 물고리를 먹어야하는 문제이기 때문에 dfs나 bfs를 이용하여 풀면된다. DFS로 풀때는 리턴 조건을 상어가 3회 모두 이동하였을때로 설정해두고, 상 좌 하 우로 이동하면서 재귀적으로 호출해주면된다. 다만, 상어가 이미 지나간 자리를 또 지나갈 수도 있게 되는데, 이때는 물고기의 횟수를 더해주면 안되므로 visited배열을 생성하여 이미 지나간 자리인지 판단해주어야 한다. BFS로 풀때는 큐를 하나 생성해서 현재좌표, 방문좌표배열, 움직인 횟수를 큐에 넣어준 후, popleft하면서 상 좌 하 우로 이동한 상태를 다시 큐에 넣어주고 이를 움직인 횟수가 3이 될때까지 반복하면된다. 

2) 메인함수는 문제에서 요구한 순서와 똑같이 작성하면된다. 물고기의 냄새를 기록하는 배열, 현재 상태 배열, 이전상태를 저장해두는 배열 3가지를 따로 관리를 해주어야한다. move함수에서 반환된 상어의 이동경로를 돌면서 물고기를 삭제해주는데, 이때 지나간 부분의 물고기의 냄새를 기록하는 배열은 3으로 초기화 해주어야한다. 이 배열은 턴을 돌면서 1씩 줄어들며 냄새가 희미해진다. (자세한 부분은 주석참고) 

 

5) 구현코드       

from copy import deepcopy
from collections import deque

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

smell = [[0] * 4 for _ in range(4)]
board = [[[] for _ in range(4)] for _ in range(4)]
m, s = map(int, input().split())
for _ in range(m):
    x, y, d = map(int, input().split())
    board[x-1][y-1].append(d-1)

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

#상어 움직이기 DFS
def move(x, y, cnt, eat, dir, visited):
    global max_eat, arr_dir 
    if cnt == 3: #3번 연속 움직이면 
        if eat > max_eat: #최댓값 업데이트
            arr_dir = deepcopy(dir)
            max_eat = eat
        return

    for d in [2, 0, 6, 4]: #상 좌 하 우 
        nx, ny = x + dx[d], y + dy[d]
        if  0 <= nx < 4 and 0 <= ny < 4:
          flag = True
          if [nx, ny] in visited: #이미 방문한 자리
              flag = False
          else: #방문하지 않은자리만 
              eat += len(board[nx][ny]) #값 추가

          if board[nx][ny]: #물고기 있으면 
              visited.append([nx, ny]) #경로추가 
          cnt += 1
          dir.append(d)

          move(nx, ny, cnt, eat, dir, visited) #재귀

          if flag: #방문하지 않은 자리였으면 
              eat -= len(board[nx][ny]) #빼주기
          if board[nx][ny]: #물고기 있었으면 
              visited.pop() #빼주기
          cnt -= 1 
          dir.pop()

#s번 반복 
for k in range(1,s+1):
    before=deepcopy(board) #이전 보드 상태 
    temp=[[[] for _ in range(4)] for _ in range(4)] #현재 보드 상태 
    #보드판 돌면서 
    for i in range(4):
      for j in range(4):
        if board[i][j]:
          #그자리에 있는 모든 물고기에 대하여 
          for d in board[i][j]:
            flag=True
            for _ in range(8): #총 8가지 방향 
              nx,ny=i+dx[d],j+dy[d]
              if 0<=nx<4 and 0<=ny<4: #보드안에 있고 
                #냄새나는 구역 아니고 상어랑도 안겹치면 
                if smell[nx][ny]==0 and not (nx==sx and ny==sy):
                  temp[nx][ny].append(d) #물고기 이동
                  flag=False
                  break
              d=(d+7)%8 #45도회전
            if flag: #물고기 이동못하는 경우
              temp[i][j].append(d)
    max_eat=-1 #최대 먹은 물고기수 
    board=temp
    move(sx,sy,0,0,deque(),deque()) #상어 이동 

    #물고기 지우면서 냄새 영역 기록 
    for d in arr_dir: #상어가 지나간 자리는 
        nx, ny = sx + dx[d], sy + dy[d]
        if board[nx][ny]: #물고기 있으면 
            board[nx][ny] = [] #사라지고 
            smell[nx][ny] = 3 #냄새가 남음
        sx, sy = nx, ny

    #냄새가 남는 곳은 턴이 지날때마다 1씩 희미해짐
    for i in range(4):
        for j in range(4):
            if smell[i][j] > 0:
              smell[i][j] -= 1
              
    #이전에 있었던 물고기 추가 
    for i in range(4):
        for j in range(4):
            if before[i][j]:
                for d in before[i][j]:
                    board[i][j].append(d)

ans = 0
for i in range(4):
    for j in range(4):
        ans += len(board[i][j])
print(ans)

 

⭐️난이도:  골드1⭐️ 

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

23290번: 마법사 상어와 복제

BFS풀이: https://chldkato.tistory.com/198

백준 23290 마법사 상어와 복제 (파이썬)

DFS풀이: https://devlibrary00108.tistory.com/662

[백준][Python][2021 하반기 삼성 코딩테스트] 23290 마법사 상어와 복제