백준: 19236 청소년 상어

문제

19236번: 청소년 상어

 

문제 풀이

 4x4 크기에 물고기들이 있고, 상어는 `(0, 0)` 부터 시작하여 물고기를 잡아먹는다. 상어는 물고기를 잡아먹으면 그 물고기의 방향에 따라서 움직일 수 있으며 해당 방향의 모든 칸에 접근이 가능하다. 상어가 물고기를 잡아먹은 후엔 물고기들은 다음과 같이 이동한다.

 

• 물고기는 한 칸씩 이동할 수 있다.
• 이동할 수 없는 칸은 4x4 크기를 벗어나는 영역이거나, 상어의 위치가 있는 영역이다.
  • 이동할 수 있을 때 까지, 방향을 45도로 회전하여 접근 가능한 곳을 접근한다.
• 접근 가능한 곳의 물고기와 자리를 전환한다.

즉 문제는 상어가 물고기를 먹고, 물고기들을 이동시키는 과정을 순차적으로 반복시키면 된다. 문제를 풀 때 설계를 잘하고 푼다면 어렵지 않게 풀 수 있는 문제이다.

 

코드

from sys import stdin
from copy import deepcopy


def visitable(x, y):
    return 0 <= x < 4 and 0 <= y < 4


def find_fish(cur_graph, fish_num):
    for x in range(4):
        for y in range(4):
            if cur_graph[x][y][FISH] == fish_num:
                return [x, y]
    return False


def dfs(sx, sy, eat, cur_graph):
    global answer

    # 현재 상어가 있는 위치의 물고기를 먹음.
    eat += cur_graph[sx][sy][FISH]
    cur_graph[sx][sy][FISH] = 0

    # 1번부터 16번까지 순차적으로 이동가능한지 확인.
    for fish_num in range(1, 17):
        loc = find_fish(cur_graph, fish_num)

        if not loc:
            continue

        fx, fy = loc[X], loc[Y]
        fish_dir = cur_graph[fx][fy][DIR]

        for z in range(8):
            # 45도씩 방향을 전환해가며 접근하도록 하기 위함.
            next_dir = (fish_dir + z) % 8
            dx, dy = dirs[next_dir]
            fnx, fny = fx + dx, fy + dy

            # 4x4 영역의 밖이고, 상어의 위치와 동일하다면 이동 불가!
            if not visitable(fnx, fny) or (fnx, fny) == (sx, sy):
                continue
            # 현재 물고기의 방향을 접근가능한 방향으로 변경.
            cur_graph[fx][fy][DIR] = next_dir
            # 접근 가능한 물고기와 스위치함.
            cur_graph[fx][fy], cur_graph[fnx][fny] = cur_graph[fnx][fny], cur_graph[fx][fy]
            break

    answer = max(answer, eat)

    shark_dir = cur_graph[sx][sy][DIR]
    # 현재 상어의 방향에서 최대 3칸 앞으로 갈 수 있음.
    for delta in range(1, 4):
        dx, dy = dirs[shark_dir]
        next_x, next_y = sx + dx * delta, sy + dy * delta

        if visitable(next_x, next_y) and cur_graph[next_x][next_y][FISH] > 0:
            dfs(next_x, next_y, eat, deepcopy(cur_graph))


if __name__ == "__main__":
    X, Y = 0, 1
    FISH, DIR = 0, 1
    answer = 0
    dirs = ((-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1))

    graph = [[[]] * 4 for _ in range(4)]

    for i in range(4):
        info = list(map(int, stdin.readline().split()))
        for j in range(4):
            graph[i][j] = [info[j * 2], info[j * 2 + 1] - 1]

    dfs(0, 0, 0, graph)
    print(answer)

 방향을 회전하기 위해서는 `%` (모듈러)를 활용하면 쉽게 전환할 수 있고, 제한 조건에 맞춰 로직을 작성하면 `맞았습니다!` 를 볼 수 있다.