[백준] 19236 : 청소년 상어 (삼성 SW 역량 테스트) / python

1. 문제 설명

19236번: 청소년 상어

문제

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

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

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

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

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

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다.

물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다.

방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

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

 

2. 풀이 전 계획과 생각

• 위의 문제는 상어가 갈 수 있는 경우의 수가 다양하고, 갈 수 있는 모든 경우를 따져 물고기 번호의 최대합을 구해야 하므로 재귀함수를 사용하여 모든 경우를 따져주었다.

 

3. 1차 풀이

EMPTY = (0, 0)
GRID_SIZE = 4
# ↑, ↖, ←, ↙, ↓, ↘, →, ↗
drs = [-1, -1, 0, 1, 1, 1, 0, -1]
dcs = [0, -1, -1, -1, 0, 1, 1, 1]

def init():
    temp_grid = [list(map(int, input().split())) for _ in range(GRID_SIZE)]
    grid = [[(0, 0) for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]
    for r in range(GRID_SIZE):
        for c in range(GRID_SIZE):
            grid[r][c] = (temp_grid[r][2 * c], temp_grid[r][2 * c + 1])

    cur_num, cur_dir = grid[0][0]
    shark_info = (-1, cur_dir)
    grid[0][0] = shark_info
    eaten = cur_num

    return grid, eaten, shark_info

def get_next(dir):
    return (dir + 1) % 8 + 1

def in_range(r, c):
    return 0 <= r < GRID_SIZE and 0 <= c < GRID_SIZE

def is_fish(r, c):
    return 1 <= grid[r][c][0] <= 16

def is_empty(r, c):
    return grid[r][c] == EMPTY

def can_fish_go(r, c):
    return in_range(r, c) and is_fish(r, c) and is_empty(r, c)

def move(fish_r, fish_c):
    fish_dir = grid[fish_r][fish_c][1]

    for _ in range(8):
        next_r, next_c = fish_r + drs[fish_dir] + fish_c + drs[fish_dir]
        if can_fish_go(next_r, next_c):
            grid[next_r][next_c], grid[fish_r][fish_c] = grid[fish_r][fish_c], grid[next_r][next_c]
            break
        fish_dir = get_next(fish_dir)
        grid[fish_r][fish_c][1] = fish_dir

def move_fish():
    for fish_num in range(1, GRID_SIZE * GRID_SIZE + 1):
        for i in range(GRID_SIZE):
            for j in range(GRID_SIZE):
                if fish_num == grid[i][j]:
                    move(fish_num, i, j)

def can_shark_go(r, c):
    return in_range(r, c) and is_fish(r, c)

def go(shark_r, shark_c, total_eaten):
    global SHARK, answer

    answer = max(answer, total_eaten)

    temp_grid = [grid[r][c] for r in range(GRID_SIZE) for c in range(GRID_SIZE)]
    temp_shark = SHARK

    move_fish()
    shark_dir = grid[shark_r][shark_c][1]

    for step in range(1, 4):
        next_r, next_c = shark_r + drs[shark_dir] * step, shark_c + dcs[shark_dir] * step
        if can_shark_go(next_r, next_c):
            # 상어 이동
            fish_num, fish_dir = grid[next_r][next_c]
            SHARK[1] = fish_dir
            grid[next_r][next_c] = SHARK
            go(next_r, next_c, total_eaten + fish_num)

            # 원래대로
            for r in range(GRID_SIZE):
                for c in range(GRID_SIZE):
                    grid[r][c] = temp_grid[r][c]
            SHARK = temp_shark

grid, initial_eaten, SHARK = init()
answer = 0
go(0, 0, initial_eaten)

print(answer)

문제점

TypeError: 'tuple' object does not support item assignment

튜플의 경우 값을 바꿀 수 없다.

ex. SHARK[1] = fish_dir

해결방안

• SHARK 표시하기 위해 (-1, -1)을 넣고 변경되지 않는 값으로 둔다.
• 상어의 방향은 매경우마다 바뀌니 재귀함수의 파라미터에 상어의 방향을 넣는다.

 

4. 2차 풀이

def init():
    grid = [[(0, 0) for _ in range(N)] for _ in range(N)]

    for r in range(N):
        row = list(map(int, input().split()))
        for c in range(N):
            grid[r][c] = (row[2 * c], row[2 * c + 1] - 1)

    return grid

def in_range(r, c):
    return 0 <= r < N and 0 <= c < N

def fish_can_go(r, c):
    return in_range(r, c) and grid[r][c] != SHARK

def get_next(cur_r, cur_c, cur_dir):
    for di in range(DIR_NUM):
        next_dir = (cur_dir + di) % DIR_NUM
        next_r, next_c = cur_r + drs[next_dir], cur_c + dcs[next_dir]
        if fish_can_go(next_r, next_c):
            return next_r, next_c, next_dir
    return cur_r, cur_c, cur_dir

def swap(cur_r, cur_c, next_r, next_c):
    grid[cur_r][cur_c], grid[next_r][next_c] = grid[next_r][next_c], grid[cur_r][cur_c]

def move_fish(target_num):
    for fish_r in range(N):
        for fish_c in range(N):
            fish_num, fish_dir = grid[fish_r][fish_c]
            if fish_num == target_num:
                next_r, next_c, next_dir = get_next(fish_r, fish_c, fish_dir)
                grid[fish_r][fish_c] = (fish_num, next_dir)
                swap(fish_r, fish_c, next_r, next_c)

def move_all_fish():
    for fish_num in range(1, N * N + 1):
        move_fish(fish_num)

def shark_can_go(r, c):
    return in_range(r, c) and grid[r][c] != BLANK

def get_max_fish_sum(cur_r, cur_c, cur_dir, cur_fish_sum):
    global answer
    answer = max(answer, cur_fish_sum)

    temp_grid = [[grid[r][c] for r in range(N)] for c in range(N)]

    for step in range(1, N):
        next_r, next_c = cur_r + drs[cur_dir] * step, cur_c + dcs[cur_dir] * step

        if shark_can_go(next_r, next_c):
            extra_fish_sum, next_dir = grid[next_r][next_c]
            grid[cur_r][cur_c], grid[next_r][next_c] = BLANK, SHARK

            get_max_fish_sum(next_r, next_c, next_dir, cur_fish_sum + extra_fish_sum)
            move_all_fish()

            for r in range(N):
                for c in range(N):
                    grid[r][c] = temp_grid[r][c]

answer = 0

N = 4
DIR_NUM = 8

drs = [-1, -1, 0, 1, 1, 1, 0, -1]
dcs = [0, -1, -1, -1, 0, 1, 1, 1]

BLANK = (0, 0)
SHARK = (-1, -1)
grid = init()

init_fish_sum, init_dir = grid[0][0]
grid[0][0] = SHARK

move_all_fish()

get_max_fish_sum(0, 0, init_dir, init_fish_sum)

print(answer)

문제점

틀렸습니다.

1. 다음 함수를 호출해야 상어를 이동한 것으로 순간 착각했다. 그래서 다음 함수를 호출하고 물고기를 이동하는 함수를 호출했다. 상어가 이동한 것은 다음함수 호출할 때가 아니라 값을 변경하고 있을 때를 말하는 것이다. 다음 함수 호출은 다음 탐색을 진행한다는 뜻이다.

⇒ 그러므로 값을 변경후 물고기를 이동시키고 다음 탐색을 진행하도록 했다.

1. 또한, 물고기 번호를 가지고 물고기를 이동 시킬 때, 격자 내에서 물고기 번호를 찾고 물고기 이동시켰으면 격자 내의 탐색을 종료해주어야 한다. 이를 까먹었다.
2. 2차원 격자 복사할 때, 반복문에서 r과 c의 순서를 뒤바꿔서 복사했다.
3. temp_grid = [ [grid[r][c] for c in range(N)] for r in range(N) ]

 

5. 3차 풀이

def init():
    grid = [[(0, 0) for _ in range(N)] for _ in range(N)]

    for r in range(N):
        row = list(map(int, input().split()))
        for c in range(N):
            grid[r][c] = (row[2 * c], row[2 * c + 1] - 1)

    return grid

def in_range(r, c):
    return 0 <= r < N and 0 <= c < N

def fish_can_go(r, c):
    return in_range(r, c) and grid[r][c] != SHARK

def get_next(cur_r, cur_c, cur_dir):
    for di in range(DIR_NUM):
        next_dir = (cur_dir + di) % DIR_NUM
        next_r, next_c = cur_r + drs[next_dir], cur_c + dcs[next_dir]
        if fish_can_go(next_r, next_c):
            return next_r, next_c, next_dir
    return cur_r, cur_c, cur_dir

def swap(cur_r, cur_c, next_r, next_c):
    grid[cur_r][cur_c], grid[next_r][next_c] = grid[next_r][next_c], grid[cur_r][cur_c]

def move_fish(target_num):
    for fish_r in range(N):
        for fish_c in range(N):
            fish_num, fish_dir = grid[fish_r][fish_c]
            if fish_num == target_num:
                next_r, next_c, next_dir = get_next(fish_r, fish_c, fish_dir)
                grid[fish_r][fish_c] = (fish_num, next_dir)
                swap(fish_r, fish_c, next_r, next_c)
                return

def move_all_fish():
    for fish_num in range(1, N * N + 1):
        move_fish(fish_num)

def shark_can_go(r, c):
    return in_range(r, c) and grid[r][c] != BLANK

def is_complete(cur_r, cur_c, cur_dir):
    for step in range(1, N):
        next_r, next_c = cur_r + drs[cur_dir] * step, cur_c + dcs[cur_dir] * step
        if shark_can_go(next_r, next_c):
            return False
    return True

def get_max_fish_sum(cur_r, cur_c, cur_dir, cur_fish_sum):
    global answer
    answer = max(answer, cur_fish_sum)

    temp_grid = [
                    [grid[r][c] for c in range(N)]
                    for r in range(N)
                ]

    for step in range(1, N):
        next_r, next_c = cur_r + drs[cur_dir] * step, cur_c + dcs[cur_dir] * step

        if shark_can_go(next_r, next_c):

            extra_fish_sum, next_dir = grid[next_r][next_c]
            grid[cur_r][cur_c], grid[next_r][next_c] = BLANK, SHARK

            move_all_fish()
            get_max_fish_sum(next_r, next_c, next_dir, cur_fish_sum + extra_fish_sum)

            for r in range(N):
                for c in range(N):
                    grid[r][c] = temp_grid[r][c]

answer = 0

N = 4
DIR_NUM = 8

drs = [-1, -1, 0, 1, 1, 1, 0, -1]
dcs = [0, -1, -1, -1, 0, 1, 1, 1]

BLANK = (0, 0)
SHARK = (-1, -1)
grid = init()

init_fish_sum, init_dir = grid[0][0]
grid[0][0] = SHARK

move_all_fish()

get_max_fish_sum(0, 0, init_dir, init_fish_sum)

print(answer)

 

6. 풀이 후 알게된 개념과 소감

• 튜플의 경우 값이 바꿀 수 없다. 튜플 안의 원소를 바꾸지 말도록 구현해야 한다.
• 백트레킹의 모든 경우를 탐색할 때 이 문제에서 "경우"란 상어가 현재 위치에서 스텝 밟으며 갈 수 있는 다음 위치들을 말한다.
• 백트레킹으로 모든 경우를 탐색할 때 감을 잡을 수 있었던 문제였다.
• 2차원 격자 복사 실수 주의! r과 c 순서 바뀌지 않게! [] 빼먹지 않게!