백준 알고리즘 19236번 청소년 상어 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

이 문제는 문제의 설명 그대로를 구 한하는 시뮬레이션 문제입니다. 저는 이 문제를 큐에 상어의 상태와 물고기들의 상태와 어항의 상태를 담아서 각 케이스마다 꺼내어 물고기들을 이동시키고, 마지막으로 상어를 이동시켰습니다. 만약 상어가 움직일 수 없다면, 정답 값을 경신하여 최종 정답 값을 출력하도록 소스코드를 작성하였습니다. 문제 설명 그대로 구현하면 되는 문제입니다. 소스코드 중간에 주석을 달아 설명을 하였습니다. 혹시 소스코드에 질문이 있으신 분들은 댓글을 남겨주시면 답변드리겠습니다. 

# 필요한 라이브러리를 불러옵니다.
import sys
from copy import deepcopy
from collections import deque
# 정답값을 담을 answer를 0으로 초기화합니다.
answer = 0
# 물고기와 상어가 8방향으로 움직일 때 사용할 방햑 벡터입니다.
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
# 4X4 보드판을 입력받을 변수 board를 선언합니다.
board = [[0] * 4 for _ in range(4)]
# 각 물고기의 x,y 좌표와 방향인 d를 저장할 3차원 원소를 가진 fish 리스트를 선언합니다.
fish = [[0, 0, 0] for _ in range(16)]
# 4번의 입력값을 통해 보드값과 물고기값을 가진 board와 fish를 갱신하여 줍니다.
for i in range(4):
    s = list(map(int, sys.stdin.readline().split()))
    for j in range(0, 8, 2):
        board[i][j // 2] = s[j]
        fish[s[j] - 1] = [i, j // 2, s[j + 1] - 1]
# 각 케이스를 담을 queue를 선언합니다.
queue = deque()
# 상어의 x,y 좌표와 방향을 담을 3차원 리스트 shark를 선언합니다.
# 상어는 처음에 0,0의 위치에 있는 물고기를 먹고 시작하므로  상어의 
# 방향은 0,0 위치의 물고기의 방향을 갖게 됩니다.
shark = [0, 0, fish[board[0][0] - 1][2]]
# 죽은 물고기의 방향을 -1로 바꿈으로써 방향이 -1인 물고기는 체크하지 않습니다.
fish[board[0][0] - 1][2] = -1
# 상어가 0,0위치의 물고기를 잡아먹고 시작하므로 0,0위치의 물고기의 점수를 더해줍니다.
score = board[0][0]
# 상어가 0,0 에 있으므로 이를 체크하기위해 보드판의 0,0을 -1로 바꿉니다.
board[0][0] = -1
# 큐에 처음 상태를 담습니다.
queue.append((board, shark, score, fish))
# 큐가 끝날 때까지 계속 코드가 돌아야 하므로 while문을 사용합니다.
while queue:
    nboard, nshark, nscore, nfish = queue.popleft()
    """
     fish 리스트에서 각 물고기를 이동시킵니다. 
     만약 방향이 -1이라면 죽은 물고기이므로 넘어가기위해
     continue를 사용합니다.
    """
    for i in range(16):
        if nfish[i][2] == -1:
            continue
        else:
            x, y, d = nfish[i]
            nx = x + dx[d]
            ny = y + dy[d]
            # 만약 물고기가 보드판위로 움직이거나 상어가 없는 곳으로 움직인다면
            if (-1 < nx < 4 and -1 < ny < 4) and nboard[nx][ny] != -1:
            	# 만약 다른 물고기가 있다면 서로 위치를 바꿉니다.
                if nboard[nx][ny] != 0:
                    temp = nboard[nx][ny]
                    nboard[nx][ny] = i + 1
                    nboard[x][y] = temp
                    nfish[i][0] = nx
                    nfish[i][1] = ny
                    nfish[temp - 1][0] = x
                    nfish[temp - 1][1] = y
                # 만약 움직이는 보드판에 물고기가 없다면 해당 보드판을 물고기가 차지합니다.
                else:
                    nfish[i][0] = nx
                    nfish[i][1] = ny
                    nboard[x][y] = 0
                    nboard[nx][ny] = i + 1

            # 가려는 곳에 갈 수 없기 때문에 45도 방향으로 회전합니다.
            else:
                for _ in range(1, 8):
                    d = (d + 1) % 8
                    nx = x + dx[d]
                    ny = y + dy[d]
                    # 가려고 하는 방향에 갈 수 있다면 위와 동일한 방식으로 처리합니다. 
                    if (-1 < nx < 4 and -1 < ny < 4) and nboard[nx][ny] != -1:
                        if nboard[nx][ny] != 0:
                            temp = nboard[nx][ny]
                            nboard[nx][ny] = i + 1
                            nboard[x][y] = temp
                            nfish[i][0] = nx
                            nfish[i][1] = ny
                            nfish[temp - 1][0] = x
                            nfish[temp - 1][1] = y
                            nfish[i][2] = d
                        else:
                            nfish[i][0] = nx
                            nfish[i][1] = ny
                            nfish[i][2] = d
                            nboard[nx][ny] = i + 1
                            nboard[x][y] = 0
                        # 이동을 하였으므로 break문을 사용하여 방향바꾸는 것을 종료합니다.
                        break
    # 상어를 움직입니다.
    sx, sy, sd = nshark
    flag = 1
    # 최대 4칸까지 움직일 수 있으므로 4번움직입니다.
    for c in range(1, 4):
        nsx = sx + c * dx[sd]
        nsy = sy + c * dy[sd]
        if -1 < nsx < 4 and -1 < nsy < 4 and nboard[nsx][nsy] > 0:
            nboard2 = deepcopy(nboard)
            nfish2 = deepcopy(nfish)
            nboard2[sx][sy] = 0
            temp = nboard2[nsx][nsy]
            nsd = nfish2[temp - 1][2]
            nfish2[temp - 1][2] = -1
            nboard2[nsx][nsy] = -1
            queue.append((nboard2, [nsx, nsy, nsd], nscore + temp, nfish2))
            flag = 0
    """상어가 움직였다면 flag를 0으로 바꾸어 아래의 if문이 실행되지 않습니다.
       따라서 아래 if 문은 상어가 더이상 움직이지 못하는 경우이고 이때 정답값을 경신합니다.
    """
    if flag:
        answer = max(answer, nscore)
# 정답값을 출력합니다.
print(answer)