[python] BOJ 백준 19236: 청소년상어

1. 문제  

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

2. 입력   

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

3. 출력   

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

4. 해결방법   

이 문제는 DFS를 이용한 구현문제이다. 결국 상어가 먹을수 있는 물고기 번호의 합의 최댓값을 구해야하기 때문에 DFS알고리즘을 이용해서 상어가 더이상 갈곳이 없을때까지의 합을 구한 후, 최대값을 업데이트 해주고, 백트래킹해서 다른 경우의수를 탐색해주는 수밖에 없다. 백트래킹 조건은 문제에 제시된대로 물고기가 없는 칸에 도달하거나, 범위를 벗어날때이다. 

1) DFS 함수: 물고기를 모두 움직여준다음, 상어를 움직인다. 상어는 백트래킹조건에 걸리기 전까지는 계속해서 이동할 수 있으며, 만약 갈곳이 없게 된다면 바로 리턴해서 종료해주면된다. 하지만 이때 글로벌 변수를 통해 최대값을 업데이트 해주어야 메인함수에서 최대값을 출력할 수 있다. DFS알고리즘으로 풀때는 항상 주의할 점이 있는데, 원데이터를 저장했다가 다시 복구해야한다는 점이다. 이렇게 하고 싶지 않으면 DFS에 계속해서 수정된 데이터값을 넣어주어야한다. 백트래킹을 한 다음에는 그 이전의 데이터로 돌아가야하는데, 이를 deepcopy함수를 이용하여 복사해놨다가, dfs 탐색이 종료되었을때에 원상복구 시켜주어야 한다. 

2) move_fish 함수: 16마리의 물고기에 대해 번호가 낮은 물고기부터 이동시킨다. 먹히지 않고 살아있는 물고기에 대하여 탐색하는데, 만약 물고기가 방향따라 이동한 곳이 범위를 넘어가거나 상어가 존재한다면 반시계 방향으로 회전해주어 갈수 있는 길을 다시 찾는다. 만약 갈 수 있는 곳에 물고기가 있으면 그곳에 존재하던 물고기는 원래 물고기가 있던 좌표로 옮겨주고, 현재 물고기는 새로 구한 좌표로 옮겨준다. 물고기가 성공적으로 이동했다면 그 물고기에 대해선 탐색을 종료하고 다음 물고기를 탐색한다. 

 

5) 구현코드   

from copy import deepcopy

#상-상좌-좌-하좌-하-하우-우-상우
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

#최대값 깊이우선탐색 
def dfs(x, y, d, eat):
    global ans, board, fish
    move_fish(x, y) #물고기 움직이기 
    while True:
        nx, ny = x + dx[d], y + dy[d] #상어움직임 
        if not 0 <= nx < 4 or not 0 <= ny < 4: #상어 갈곳없음 
            ans = max(ans, eat) #최대값 업데이트 
            return #종료 
        if not board[nx][ny]: #물고기 없음 
            x, y = nx, ny #다음좌표로 이동 
            continue

        temp_board, temp_fish = deepcopy(board), deepcopy(fish) #원 데이터 저장 
        dir,num  = fish[board[nx][ny][0]], board[nx][ny] #물고기배열, 보드배열 데이터저장
        fish[board[nx][ny][0]], board[nx][ny] = [], [] #먹은 자리 초기화 
        dfs(nx, ny, num[1], eat + num[0] + 1) # 상어좌표, 상어방향, 누적값 
        #원래대로 되돌리기 
        board, fish = temp_board, temp_fish
        fish[board[nx][ny][0]], board[nx][ny] = dir, num
        x, y = nx, ny #다음좌표로 이동 

#물고기 움직이기
def move_fish(sx, sy): 
    for i in range(16):
        if fish[i]:
            x, y = fish[i][0], fish[i][1] #물고기 좌표 
            for _ in range(9): #반시계방향으로 움직이면서 
                d=board[x][y][1]
                nx, ny = x + dx[d], y + dy[d] 
                if not 0 <= nx < 4 or not 0 <= ny < 4 or (nx == sx and ny == sy):
                    board[x][y][1] = (board[x][y][1] + 1) % 8 #반시계방향으로 회전 
                    continue
                if board[nx][ny]: #물고기 있으면 
                    fish[board[nx][ny][0]] = [x, y]  #그쪽에 있는 물고기 옮기기 
                board[nx][ny], board[x][y] = board[x][y], board[nx][ny] #자리교체 
                fish[i] = [nx, ny] #물고기 좌표 업데이트 
                break 


board = [[] for _ in range(4)]
fish = [[] for _ in range(16)]

for i in range(4):
    temp = list(map(int, input().split()))
    for j in range(0, 7, 2):
        board[i].append([temp[j]-1, temp[j+1]-1]) #번호, 방향 
        fish[temp[j]-1] = [i, j // 2] #물고기 x좌표, y좌표 

ans = 0
d, eat = board[0][0][1], board[0][0][0] + 1 #상어방향, 먹은물고기번호 
fish[board[0][0][0]], board[0][0] = [], [] #0,0 좌표 초기화 
dfs(0, 0, d, eat) 
print(ans)

 

⭐️난이도:  골드 2⭐️

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

19236번: 청소년 상어