[백준] 19236 청소년 상어 (by Python)

문제 - 골드2

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

19236번: 청소년 상어

문제 설명

문제 조건에 따라 DFS를 활용해서 구현하는 문제이다. 

문제 조건만 잘 정리해서 구현하면 되는데, 아직 익숙하지 않아 어려웠다.

 

문제 목표

상어가 먹을 수 있는 물고기 번호의 합의 최댓값 찾기 -> 시뮬레이션 문제 + DFS

 

문제 조건

1. 상어가 (0, 0)에 있는 물고기 먹기

• 한 칸에 물고기 한마리 존재, (물고기 번호, 방향)으로 주어짐
• 상어가 물고기를 먹으면, 물고기 방향과 동일해짐

2. 물고기 모두 이동

• 물고기는 번호 순서대로 한 칸씩 이동, 45도 반시계 회전
• 이동이 가능한 경우: 다른 물고기와 서로 위치 바꾸기, 빈칸일 경우
• 이동이 불가능한 경우: 상어 존재, 경계 넘을 경우(이동할 수 없으면 그대로)

3. 상어 이동

• 물고기 이동 모두 끝나면 상어 이동
• 한 번에 여러칸 이동 가능
• 지나가는 칸에서는 물고기 먹지 않음
• 이동할 수 없는 칸이 없으면 종료

구현하기

1. 물고기 번호 순서대로 찾기

# 1) 물고기 순서대로 죄표찾기
def find_fish(graph, fish):
    for i in range(n):
        for j in range(n):
            if graph[i][j][0] == fish:
                return (i, j)

 

2. 모든 물고기 이동 - 물고기 순서대로 좌표를 find_fish를 통해 찾은 후 물고기가 이동할 수 있으면 이동하기

# 2) 모든 물고기 이동
def move_fish(x, y, graph):
    # 1 ~ 16번 순으로 물고기 이동
    for fish_num in range(1, 17):
        # 물고기 좌표 찾기
        position = find_fish(graph, fish_num)
        # 해당 물고기가 존재하는 경우
        if position:
            x_fish, y_fish = position[0], position[1] # 물고기 좌표 리턴받기
            direction = graph[x_fish][y_fish][1] # 현재 물고기 방향 저장
            # 반시계 방향으로 45도 회전하며 확인
            for _ in range(len(dir)): # 방향 수 만큼 회전해보기
                nx_fish = x_fish + dir[direction][0]
                ny_fish = y_fish + dir[direction][1]
                # 맵 내부에 위치한 경우
                if 0 <= nx_fish < n and 0 <= ny_fish < n:
                    # 이동할 곳에 상어가 없는 경우
                    if not (nx_fish == x and ny_fish == y):
                        # 해당 방향으로 이동
                        graph[x_fish][y_fish][1] = direction # 현재 물고기 방향으로 바꾸기
                        # 물고기 간에 위치 변경
                        graph[nx_fish][ny_fish],graph[x_fish][y_fish] = graph[x_fish][y_fish], graph[nx_fish][ny_fish]
                        break # 진행 방향이 확정됐으니까 중단
                direction = (direction + 1) % len(dir) # 다음 방향

 

3. 상어가 이동 가능한 좌표 찾기

# 1) 상어의 이동가능한 좌표 찾기
def movable_shark(x, y, graph):
    direction = graph[x][y][1] # 상어 진행 방향
    position = []
    for _ in range(n-1):
        # 진행방향으로 전진
        x += dir[direction][0]
        y += dir[direction][1]
        # 진행 후 맵 내부에 있고, 물고기가 존재하는 경우
        if 0 <= x < n and 0 <= y < n and graph[x][y][0] != -1:
            position.append((x, y))
    return position

 

4. 물고기 먹고, 끝날 때 까지 상어 이동

# 2) 물고기 먹고 상어 탈출할 때 까지 상어 이동

def dfs(x, y, sum, graph):
    global answer
    graph = copy.deepcopy(graph) # 그래프 복사
    # 상어가 해당 물고기 먹음
    sum += graph[x][y][0]
    graph[x][y][0] = -1 # 잡아먹힘 표시하기
    move_fish(x, y, graph) # 모든 물고기 이동
    # 상어가 이동가능한 좌표 리턴받기
    position = movable_shark(x, y, graph)

    # 이동 가능 좌표가 존재하는 경우
    if position:
        for nx, ny in position:
            dfs(nx, ny, sum, graph) # 반복
    else:
        answer = max(answer, sum) # 최대값으로 갱신
        return

 

5. main 코드

if __name__ == '__main__':
    n = 4
    graph = [[0]*n for _ in range(n)]
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            # 물고기 번호, 방향 정보 저장 
            graph[i][j] = [data[2*j], data[2*j+1]-1]

    # 진행방향: 상, 좌상, 좌, 좌하, 하, 우하, 우, 우상
    dir = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
    # (0, 0)에서 시작
    x = y = 0
    answer = 0
    dfs(x, y, 0, graph)
    print(answer)

 

최종 코드

# 목표) 최대 먹을 수 있는 양
# DFS
import copy
import sys
input = sys.stdin.readline

# (0,0)에서 물고기 먹기

# 물고기 순회 완료

# 1) 물고기 순서대로 죄표찾기
def find_fish(graph, fish):
    for i in range(n):
        for j in range(n):
            if graph[i][j][0] == fish:
                return (i, j)

# 2) 모든 물고기 이동
def move_fish(x, y, graph):
    # 1 ~ 16번 순으로 물고기 이동
    for fish_num in range(1, 17):
        # 물고기 좌표 찾기
        position = find_fish(graph, fish_num)
        # 해당 물고기가 존재하는 경우
        if position:
            x_fish, y_fish = position[0], position[1] # 물고기 좌표 리턴받기
            direction = graph[x_fish][y_fish][1] # 먹은 물고기 방향 저장
            # 반시계 방향으로 45도 회전하며 확인
            for _ in range(len(dir)): # 방향 수 만큼 회전해보기
                nx_fish = x_fish + dir[direction][0]
                ny_fish = y_fish + dir[direction][1]
                # 맵 내부에 위치한 경우
                if 0 <= nx_fish < n and 0 <= ny_fish < n:
                    # 이동할 곳에 상어가 없는 경우
                    if not (nx_fish == x and ny_fish == y):
                        # 해당 방향으로 이동
                        graph[x_fish][y_fish][1] = direction # 먹은 물고기 방향으로 바꾸기
                        # 물고기 간에 위치 변경
                        graph[nx_fish][ny_fish],graph[x_fish][y_fish] = graph[x_fish][y_fish], graph[nx_fish][ny_fish]
                        break # 진행 방향이 확정됐으니까 중단
                direction = (direction + 1) % len(dir) # 다음 방향

# 본격적인 상어 사냥 시작

# 1) 상어의 이동가능한 좌표 찾기
def movable_shark(x, y, graph):
    direction = graph[x][y][1] # 상어 진행 방향
    position = []
    for _ in range(n-1):
        # 진행방향으로 전진
        x += dir[direction][0]
        y += dir[direction][1]
        # 진행 후 맵 내부에 있고, 물고기가 존재하는 경우
        if 0 <= x < n and 0 <= y < n and graph[x][y][0] != -1:
            position.append((x, y))
    return position

# 2) 물고기 먹고 상어 탈출할 때 까지 상어 이동

def dfs(x, y, sum, graph):
    global answer
    graph = copy.deepcopy(graph) # 그래프 복사
    # 상어가 해당 물고기 먹음
    sum += graph[x][y][0]
    graph[x][y][0] = -1 # 잡아먹힘 표시하기
    move_fish(x, y, graph) # 모든 물고기 이동
    # 상어가 이동가능한 좌표 리턴받기
    position = movable_shark(x, y, graph)

    # 이동 가능 좌표가 존재하는 경우
    if position:
        for nx, ny in position:
            dfs(nx, ny, sum, graph) # 반복
    else:
        answer = max(answer, sum) # 최대값으로 갱신
        return
if __name__ == '__main__':
    n = 4
    graph = [[0]*n for _ in range(n)]
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            # 물고기 번호, 방향 정보 저장 
            graph[i][j] = [data[2*j], data[2*j+1]-1]

    # 진행방향: 상, 좌상, 좌, 좌하, 하, 우하, 우, 우상
    dir = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
    # (0, 0)에서 시작
    x = y = 0
    answer = 0
    dfs(x, y, 0, graph)
    print(answer)