[백준(BOJ)] #19236- 청소년 상어 (파이썬, PyPy3)

문제

 

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

19236번: 청소년 상어

 

---

문제 풀이

 

이 문제는 구현 문제로 DFS 알고리즘을 적용하여 풀었습니다.

DFS 알고리즘 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

역시 구현 문제는 조건을 잘 이해하고, 고려해야 하기 때문에 꽤 오래 걸렸네요..ㅠ 

물고기의 움직임과 상어의 움직임을 잘 고려해서 풀어나가야 합니다!

 

물고기의 움직임

 

각 물고기는 1부터 16까지의 중복되지 않는 번호를 가지고 있습니다. 1번 물고기부터 순서대로 가지고 있는 방향대로 1만큼 움직일 수 있고, 범위는 2차원 리스트 내부이며 상어가 있는 방향으로는 움직일 수 없습니다. 움직이는 곳에 다른 물고기가 있으면 그 물고기와 위치가 바뀝니다.

 

또한 제일 중요한 조건은 기존의 방향이 위의 조건을 만족하지 못하여 이동을 못하면 반시계 방향으로 45도만큼 방향을 틀어서 이동할 수 있는지 검사를 합니다. 이동할 수 있으면 이 방향을 기존 방향으로 설정하고 이동을 합니다.

저는 여기에서 로직을 조금 잘못짜서 오래 걸리게 되었습니다.... ㅎㅎ

 

 

1) 2번 물고기의 기존 이동 방향이 1번(위쪽 방향) 일 때 1번 방향 검사. -1은 상어라고 가정. 상어가 있으므로 해당 방향으로는 이동할 수 없음.

 

2) 2, 3, 4 방향은 범위 밖에 있으므로 이동할 수 없음.

 

3) 해당 방향에는 상어도 없고, 범위 내부에 있으므로 이동 가능.

 

4) 수정된 방향이 기존 방향이 되고, 7번 물고기와 자리가 바뀌게 됨.

 

 

상어의 움직임

 

상어는 (0, 0) 자리에 있는 물고기를 먹고 시작합니다. 상어는 물고기와 달리 가리키는 방향에 있는 물고기를 모두 먹을 수 있습니다. 단 한 움직임당 한 마리만 먹을 수 있습니다. 

경우의 수를 따져봐야 하기 때문에 DFS 알고리즘을 사용하여 같은 방향에 있는 모든 물고기에 대해 재귀 호출을 하여 해당 물고기의 번호를 누적하였고, 베이스 케이스로는 해당 방향이 막혀있거나 물고기가 없는 경우로 하여 호출을 종료하였습니다. dfs 알고리즘을 적용할 때에는 리스트를 deepcopy로 복사하여 백트래킹을 할 수 있도록 하였습니다.

 

백트래킹(Backtracking)이란?

경우의 수를 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식으로, 조건에 맞지 않으면 중단하여 이전으로 돌아가 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘

---

구현

코드

import sys
import copy
input = sys.stdin.readline

# 8가지 방향 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 순서로
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 물고기 이동
def fish_move(t_board):
    for i in range(1, 17):
        is_there = False
        f_pos = None
        for j in range(4):
            for k in range(4):
                if t_board[j][k][0] == i:
                    is_there = True
                    f_pos = [j, k]
                    break
        # 해당 번호의 물고기가 존재하면
        if is_there:
            dir = t_board[f_pos[0]][f_pos[1]][1]
            dir -= 1
            x = f_pos[0] + dx[dir]
            y = f_pos[1] + dy[dir]
            cnt = 0
            # 상어가 없거나 범위 내에 있을 때 까지 방향 전환
            while not(0 <= x < 4 and 0 <= y < 4 and t_board[x][y][0] != -1):
                dir += 1
                if dir > 7:
                    dir -= 8
                x = f_pos[0] + dx[dir]
                y = f_pos[1] + dy[dir]
                cnt += 1
                if cnt == 7:
                    break
            # 모든 방향을 탐색해도 조건을 만족하지 못할경우에는 cnt == 7로 이동할 수 없음
            if cnt < 7:
                t_board[f_pos[0]][f_pos[1]][1] = dir + 1
                t_board[f_pos[0]][f_pos[1]][0], t_board[x][y][0] = t_board[x][y][0], t_board[f_pos[0]][f_pos[1]][0]
                t_board[f_pos[0]][f_pos[1]][1], t_board[x][y][1] = t_board[x][y][1], t_board[f_pos[0]][f_pos[1]][1]

# 상어 이동
def dfs(x, y, dir, score, t_board):
    global max_score
    # 해당 자리에 상어 위치
    t_board[x][y][0] = -1
    # 물고기 이동
    fish_move(t_board)
    t_board[x][y][0] = 0
    is_block = True

	# i만큼 떨어진 위치에 물고기 탐색
    for i in range(1, 5):
        xx = x + dx[dir-1]*i
        yy = y + dy[dir-1]*i
        # 해당 위치가 범위 내에 있거나 물고기가 있으면
        if 0 <= xx < 4 and 0 <= yy < 4 and t_board[xx][yy][0] != 0:
            is_block = False
            # 해당 위치로 재귀 호출
            dfs(xx, yy, t_board[xx][yy][1], score + t_board[xx][yy][0], copy.deepcopy(t_board))
    # 막혀있거나 물고기가 없으면 점수 계산
    if is_block:
        max_score = max(max_score, score)
        return
    

if __name__ == "__main__":
    board = [[] for _ in range(4)]
    max_score = 0

    for i in range(4):
        a = list(map(int, input().split()))
        for j in range(0, 8, 2):
            board[i].append([a[j], a[j+1]])
 
    dfs(0, 0, board[0][0][1], board[0][0][0], copy.deepcopy(board))
    print(max_score)

 

결과