[백준/19236/파이썬] 청소년 상어

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

19236번: 청소년 상어

Problem

• 오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
• 4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다.
• 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다.
• 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
• 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

조건

• 물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
• 물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

SOL

초등학생 상어, 어른 상어 문제를 푸니까 , 이번에는 청소년 상어가 나왔다.

상어들이 왜이렇게 많을까 , 우리나라는 사실 상어 강국?

 

구현하는데는 큰 무리가 없었지만, 중간에 물고기가 움직이는 부분을 따로 함수로 처리해줬었는데,

거기서, 물고기가 죽은 정보가 제대로 반영이 되지않는 오류가 발생했었다.

결국 원인은 찾지못한채로, 일단 DFS 구문안에 그때마다 찾아서 물고기를 움직여주는걸로 바꿔주었다. :(

# 청소년 상어 ~

# 상어가 움직이는 부분
# 물고기가 이동하는 부분
# 물고기는 번호 순서대로 이동한다.
# 물고기는 이동할 곳이 없으면, 방향을 돈다. (반시계방향 45도)
# 상어는 먹은 물고기의 방향으로 움직인다.(방향에 있는 어떤 물고기든 다 먹을수 있음.)
import sys
import copy
sys.setrecursionlimit(10**6)
input= sys.stdin.readline

board=[[0 for _ in range(4)] for _ in range(4)]
fishLst=[x for x in range(17)]
dx=[0,-1,-1,-1,0,1,1,1]
dy=[-1,-1,0,1,1,1,0,-1]

tmp = [list(map(int,input().split())) for _ in range(4)]
for i in range(4):
    for j in range(4):
        board[i][j] = [tmp[i][j*2],tmp[i][j*2+1]-1]

#print(board)
#init
ans=0
def dfs(sy,sx,score,board):
    global ans
    score +=board[sy][sx][0]
    ans=max(ans,score)
    board[sy][sx][0] =0
    #물고기가 움직여요. 물고기 정보도 반영해줍니다.
    for f in range(1,17):
        #물고기가 잡아 먹혔는지, 안잡아먹혔는지 check
        loc =None
        for y in range(4):
            for x in range(4):
                if board[y][x][0] ==f:
                    loc =(y,x)
        if not loc:
            continue
        # 물고기가 살아 있다면, 방향을 돌려준다.
        y,x =loc
        fdir =board[y][x][1]
        for k in range(8):
            nd =(fdir+k)%8
            ny = y+dy[nd]
            nx = x+dx[nd]
            if not (0<=ny<4 and 0<=nx<4) or (ny==sy and nx==sx):
                continue
            board[y][x][1] = nd
            board[y][x],board[ny][nx] = board[ny][nx],board[y][x]
            break
    
    #fish_moving(sy,sx)
    # 상어가 움직인다
    s_d=board[sy][sx][1]
    for k in range(1,5):
        ny=sy+dy[s_d]*k
        nx=sx+dx[s_d]*k
        if (0<=ny<4 and 0<=nx<4) and board[ny][nx][0]>0:
            dfs(ny,nx,score,copy.deepcopy(board))

dfs(0,0,0,board)
print(ans)