[Python] n19236번 | 청소년 상어

 

격자 크기 : 4
위치 : X,Y
한 칸에는 물고기 1마리
물고기 (번호,방향) >> 1<=번호<=16, 방향은 8가지

---

1. 물고기를 먹는다.
2. 물고기가 있던 칸에 들어간다.
3. 상어의 방향 = 먹힌 물고기의 방향
4. 물고기 이동
- 작은 물고기부터 순서대로 이동한다. (물고기는 한 번에 한 칸 이동 가능)
( 조건 : 이동할 수 있는 칸 : 빈 칸, 다른 물고기가 있는 칸, 이동할 수 없는 칸 : 상어가 있는 칸, 격자 밖)
- 이동할 수 있는 칸을 향할때까지 45도 반시계 방향으로 회전한다.
- 이동할 수 있는 칸이 없으면? 이동 X
- 그 외의 경우엔 그 칸으로 이동
- 물고기가 다른 물고기가 있는 칸으로 갈 땐, 서로의 위치를 바꾼다.

물고기의 이동이 모두 끝난 후
5. 상어의 이동
- 상어는 한 번에 여러 개의 칸 이동 가능 (이동하며 지나가는 칸의 물고기는 먹지 X)
- 상어의 방향쪽으로만 이동이 가능하다. ->이면 ->쪽에 있는 물고기로만 이동이 가능.
- 물고기 있는 칸으로 이동 : 물고기 먹고, 물고기 방향 GET
- 이동할 수 없는 칸 : 물고기가 없는 칸
- 만약 이동할 수 없는 상태이면? 공간에서 벗어나 집으로 간다.

상어가 이동한 후에는 다시 물고기가 이동하며 이 과정이 반복

>> 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구하라.

DFS와 백트래킹의 차이점
DFS : 모든 경우의 수를 전부 확인하는 알고리즘이다.
백트래킹 : 모든 경우의 수를 확인하지 않는다. 스택에 자식노드를 넣기 전에 유망한지 확인 후 스택에 넣는다.
왜 이 문제가 DFS문제인가?
   > 모든 노드를 검사해서, 값을 구해야하기 때문이다.
       왜 이 문제가 백트래킹문제인가?
       > 상어가 먹을 수 있는 물고기만 파악하면 되니까 모든 노드를 검색해도 되지 않기 때문이다

---

import copy

array = [[None] * 4 for _ in range(4)]

for i in range(4):
    data = list(map(int, input().split()))
    # 매 줄마다 4마리의 물고기를 하나씩 확인하며
    for j in range(4):
        # 각 위치마다 [물고기의 번호, 방향]을 저장
        array[i][j] = [data[j * 2], data[j * 2 + 1] - 1]

# 8가지 방향에 대한 정의
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]


# 현재 위치에서 왼쪽으로 회전된 결과 반환
def turn_left(direction):
    return (direction + 1) % 8


result = 0  # 최종 결과


# 현재 배열에서 특정한 번호의 물고기 위치 찾기
def find_fish(array, index):
    for i in range(4):
        for j in range(4):
            if array[i][j][0] == index:
                return (i, j)
    return None


# 모든 물고기를 회전 및 이동시키는 함수
def move_all_fishes(array, now_x, now_y):
    # 1번부터 16번까지의 물고기를 차례대로 (낮은 번호부터) 확인
    for i in range(1, 17):
        # 해당 물고기의 위치를 찾기
        position = find_fish(array, i)
        if position != None:
            x, y = position[0], position[1]
            direction = array[x][y][1]
            direction = array[x][y][1]
            # 해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
            for j in range(8):
                nx = x + dx[direction]
                ny = y + dy[direction]
                # 해당 방향으로 이동이 가능하다면 이동 시키기
                if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
                    if not (nx == now_x and ny == now_y):
                        array[x][y][1] = direction
                        array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
                        break
                direction = turn_left(direction)


# 상어가 현재 위치에서 먹을 수 있는 모든 물고기의 위치 반환
def get_possible_positions(array, now_x, now_y):
    positions = []
    direction = array[now_x][now_y][1]
    # 현재의 방향으로 쭉 이동하기
    for i in range(4):
        now_x += dx[direction]
        now_y += dy[direction]
        # 범위를 벗어나지 않는지 확인하며
        if 0 <= now_x and now_x < 4 and 0 <= now_y and now_y < 4:
            # 물고기가 존재하는 경우
            if array[now_x][now_y][0] != -1:
                positions.append((now_x, now_y))
    return positions


# 모든 경우를 탐색하기 위한 DFS 함수
def dfs(array, now_x, now_y, total):
    global result
    array = copy.deepcopy(array)  # 리스트를 통째로 복사

    total += array[now_x][now_y][0]  # 현재 위치의 물고기 먹기
    array[now_x][now_y][0] = -1  # 물고기를 먹었으므로 번호 값을 -1로 변환

    move_all_fishes(array, now_x, now_y)
    # 이제 다시 상어가 이동할 차례이므로, 이동 가능한 위치 찾기
    positions = get_possible_positions(array, now_x, now_y)
    # 이동할 수 있는 위치가 하나도 없다면 종료
    if len(positions) == 0:
        result = max(result, total)  # 최댓값 저장
        return
        # 모든 이동할 수 있는 위치로 재귀적으로 수행
    for next_x, next_y in positions:
        dfs(array, next_x, next_y, total)

    return array

# 청소년 상어의 시작 위치(0, 0)에서부터 재귀적으로 모든 경우 탐색
dfs(array, 0, 0, 0)
print(result)

---

참고출처 : github.com/ndb796/python-for-coding-test/blob/master/19/2.py

ndb796/python-for-coding-test

문제 출처 : www.acmicpc.net/problem/19236

19236번: 청소년 상어