[python] 청소년 상어 (dfs)

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

19236번: 청소년 상어

 

 

처음에 엥 이게 왜 dfs 문제지? 하고 while True 문을 이용해 물고기 이동, 제일 덩치 큰(번호가 높은) 물고기를 골라 상어의 식사를 마치고 상어가 벽을 만나면 그대로 종료하는 식으로 풀이하였다.

그러나.. 이 문제는 '상어가 먹을 수 있는 물고기 번호의 최댓값을 구하는 문제'이다. 따라서 벽을 만나지 않으면서 최대한 많은 물고기를 잡아먹도록 구현해야 한다. 그렇기 때문에 dfs 방식의 접근이 필요한 것이다.  

 

예를 들어, 다음과 같이 물고기의 이동이 진행되었다고 한다면 상어는 대각선 오른쪽 아래 방향으로만 이동이 가능하다. 여기에서 상어가 식사할 수있는 물고기 번호는 14, 7, 16이다. 만약 16을 고른다면 최대 물고기 번호를 당장 야무지게 식사할 수 있다. 하지만

다음과 같은 곳에 상어가 위치한다면 상어의 방향이 오른쪽 아래 대각선 방향을 향한다. 즉, 물고기 이동이 진행된 이후 상어는 무조건 벽을 만나게 되므로 16번밖에 못먹고 끝이 난다.  

 

따라서 상어가 물고기 식사를 할 때 dfs 탐색을 진행하여 최대한 벽에 닿지 않으면서 야무진 식사를 할 수 있도록 구현해야 한다.  

 

* 문제를 풀기 위해 필요한 아이디어 

1) 상어가 식사할 수 있는 모든 물고기 좌표에 대해 dfs 탐색하기  

2) dfs 탐색시 방향 정보가 담긴 테이블과 물고기 번호, 상어 정보가 담긴 테이블 깊이 복사하기   

 

 

1. 코드 개선 

import copy

# 1 2 3 4 5 6 7 8
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 반시계로 회전
def turn45(D):
    return (D+1)%8

# 물고기 이동
def fish_move(d_arr, s_arr, x, y):
    # 1~16까지 물고기 move
    for k in range(1, 17):
        # 잡아 먹힌 물고기는 무시
        xx, yy = find_fish(s_arr, k)
        if xx == -1 and yy == -1:
            continue

        D = d_arr[xx][yy]
        # 이동이 가능한 경우 물고기 위치 방향 정보 swap
        for _ in range(8):
            fx, fy = xx + dx[D], yy + dy[D]
            # 벽이거나 상어가 있는 경우 회전
            if fx < 0 or fx >= 4 or fy < 0 or fy >= 4 or (fx == x and fy == y):
                D = turn45(D)
            else:
                # 방향 정보 갱신
                d_arr[xx][yy] = D
                # 물고기 교환
                s_arr[xx][yy], s_arr[fx][fy] = s_arr[fx][fy], s_arr[xx][yy]
                d_arr[xx][yy], d_arr[fx][fy] = d_arr[fx][fy], d_arr[xx][yy]
                break

# 상어가 이동 가능한 좌표 구하기
def possible_move(d_arr, s_arr, x, y):
    positions = []
    d = d_arr[x][y]
    # 상어가 위치할 수 있는 좌표 정보 확인
    for _ in range(4):
        x += dx[d]
        y += dy[d]
        if 0 <= x < 4 and 0 <= y < 4:
            if s_arr[x][y] != 0:
                positions.append([x, y])
    return positions

# 물고기 위치 찾기
def find_fish(arr, K):
    for i in range(4):
        for j in range(4):
            if arr[i][j] == K:
                return [i, j]
    # 상어가 식사해버려서 번호를 못찾는 경우
    return [-1, -1]

result = 0
space = [[0]*4 for _ in range(4)]
direction = [[0]*4 for _ in range(4)]
for i in range(4):
    data = list(map(int, input().split()))
    for j in range(4):
        # 처음에 저장할 때 방향 정보 -1 처리
        space[i][j], direction[i][j] = data[j*2], data[j*2+1]-1
  
def dfs(d_arr, s_arr, x, y, total):
    global result, space
    s_arr = copy.deepcopy(s_arr)  # 리스트를 통째로 복사
    d_arr = copy.deepcopy(d_arr)
    total += s_arr[x][y] # 물고기 식사
    s_arr[x][y] = 0 # 잡아 먹힌 물고기 제거
    # 물고기 이동
    fish_move(d_arr, s_arr, x, y)

    # 상어 move
    p = possible_move(d_arr, s_arr, x, y)
    # 더이상 이동 불가능한 경우  
    if not p:
        result = max(total, result)
        return
    # 상어가 이동 가능한 경로에 대해 깊이 탐색
    for next_x, next_y in p:
        dfs(d_arr, s_arr, next_x, next_y, total)

dfs(direction, space, 0, 0, 0)
print(result)

 

1. 구현 

import copy

# 1 2 3 4 5 6 7 8
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 반시계로 회전
def turn45(D):
    if D == 8:
        return 1
    return D+1

# 물고기 이동
def fish_move(d_arr, s_arr, x, y):
    # 1~16까지 물고기 move
    for k in range(1, 17):
        # 잡아 먹힌 물고기는 무시
        xx, yy = find_fish(s_arr, k)
        if xx == -1 and yy == -1:
            continue

        D = d_arr[xx][yy]
        # 이동이 가능한 경우 물고기 위치 방향 정보 swap
        for _ in range(8):
            fx, fy = xx + dx[D-1], yy + dy[D-1]
            # 벽이거나 상어가 있는 경우 회전
            if fx < 0 or fx >= 4 or fy < 0 or fy >= 4 or (fx == x and fy == y):
                D = turn45(D)
            else:
                # 방향 정보 갱신
                d_arr[xx][yy] = D
                # 물고기 교환
                s_arr[xx][yy], s_arr[fx][fy] = s_arr[fx][fy], s_arr[xx][yy]
                d_arr[xx][yy], d_arr[fx][fy] = d_arr[fx][fy], d_arr[xx][yy]
                break

# 상어가 이동 가능한 좌표 구하기
def possible_move(d_arr, s_arr, x, y):
    global result

    positions = []
    sd = d_arr[x][y]
    # 상어가 위치할 수 있는 좌표 정보 확인
    for _ in range(4):
        x += dx[sd-1]
        y += dy[sd-1]
        if 0 <= x < 4 and 0 <= y < 4:
            if s_arr[x][y] != 0:
                positions.append([x, y])
    return positions

# 물고기 위치 찾기
def find_fish(arr, K):
    for i in range(4):
        for j in range(4):
            if arr[i][j] == K:
                return [i, j]
    # 상어가 이미 식사해버려서 번호를 못찾는 경우
    return [-1, -1]

result = 0
space = [[0]*4 for _ in range(4)]
direction = [[0]*4 for _ in range(4)]
for i in range(4):
    x1, d1, x2, d2, x3, d3, x4, d4 = map(int, input().split())
    space[i][0], direction[i][0] = x1, d1
    space[i][1], direction[i][1] = x2, d2
    space[i][2], direction[i][2] = x3, d3
    space[i][3], direction[i][3] = x4, d4


def dfs(d_arr, s_arr, x, y, total):
    global result, space
    s_arr = copy.deepcopy(s_arr)  # 리스트를 통째로 복사
    d_arr = copy.deepcopy(d_arr)
    total += s_arr[x][y] # 물고기 식사
    s_arr[x][y] = 0 # 잡아먹힌 물고기 제거
    # 물고기 이동
    fish_move(d_arr, s_arr, x, y)

    # 상어 move
    p = possible_move(d_arr, s_arr, x, y)
    # 식사 가능한 물고기가 없는 경우  
    if not p:
        result = max(total, result)
        return
    # 상어가 식사 가능한 물고기 좌표에 대해 깊이 탐색
    for next_x, next_y in p:
        dfs(d_arr, s_arr, next_x, next_y, total)


dfs(direction, space, 0, 0, 0)
print(result)

 

 

2. 틀린 풀이

# 1 2 3 4 5 6 7 8
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 반시계로 회전
def turn45(D):
    if D == 8:
        return 1
    return D+1

# 물고기 이동
def fish_move(xx, yy):
    D = direction[xx][yy]
    # 이동 가능한 경우와 이동이 불가능한 경우 나눔
    # 이동이 가능한 경우 물고기 위치 방향 정보 swap
    # 이동이 불가능한 경우 stay
    for _ in range(8):
        fx, fy = xx + dx[D-1], yy + dy[D-1]
        # 벽이거나 상어가 있는 경우 회전
        if fx < 0 or fx >= 4 or fy < 0 or fy >= 4 or (fx == x and fy == y):
            D = turn45(D)
        else:
            # 방향 정보 갱신
            direction[xx][yy] = D
            # 물고기 교환
            space[xx][yy], space[fx][fy] = space[fx][fy], space[xx][yy]
            direction[xx][yy], direction[fx][fy] = direction[fx][fy], direction[xx][yy]
            break

def shark_move():
    global result, x, y
    # print('x, y', x, y,'에 있는 상어가 움직입니다..')
    positions = []
    # 그 방향으로 이동 가능한지 여부를 먼저 판단해야함
    # 이동할 수 없다면 집으로 가야함 : 종료 
    # 회전은 못함
    # 상어의 좌표, 상어의 방향
    sx, sy = x, y
    sd = direction[x][y]
    # 상어가 위치할 수 있는 좌표 정보 확인
    for _ in range(4):
        sx += dx[sd-1]
        sy += dy[sd-1]
        if 0 <= sx < 4 and 0 <= sy < 4:
            if space[sx][sy] != 0:
                positions.append([space[sx][sy], sx, sy])
    # 이동가능한 경로가 없는 경우
    if not positions:
        return False
    # 최댓값이 담긴 물고기 번호를 식사 <- 문제가 되는 부분 (1)
    positions.sort(key=lambda x:-x[0])
    result += positions[0][0]
    # print(space[positions[0][1]][positions[0][2]], '오늘의 먹이!')
    space[positions[0][1]][positions[0][2]] = 0
    x, y = positions[0][1], positions[0][2]
    # print('냠냠 쩝쩝 잘먹었습니다')
    return True

def find_fish(K):
    for i in range(4):
        for j in range(4):
            if space[i][j] == K:
                return [i, j]
    # 상어가 식사해버려서 번호를 못찾는 경우 
    return False

result = 0
space = [[0]*4 for _ in range(4)]
direction = [[0]*4 for _ in range(4)]
for i in range(4):
    x1, d1, x2, d2, x3, d3, x4, d4 = map(int, input().split())
    space[i][0], direction[i][0] = x1, d1
    space[i][1], direction[i][1] = x2, d2
    space[i][2], direction[i][2] = x3, d3
    space[i][3], direction[i][3] = x4, d4

x, y = 0, 0
result += space[x][y]
# 잡아 먹힌 물고기 삭제
space[x][y] = 0

while True: # 문제가 되는 부분 (2)
    # 1~16까지 물고기 move
    for k in range(1, 17):
        # 잡아 먹힌 물고기는 무시
        if not find_fish(k):
            continue
        find_x, find_y = find_fish(k)
        fish_move(find_x, find_y)

    # 상어 move
    if not shark_move():
        break
print(result)