[DFS] 백준#19236: 청소년 상어/Python

📝 문제

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

19236번: 청소년 상어

백준 내 아기 상어 문제의 후속 버전입니다.

💡 접근법

• 사용 알고리즘: DFS 알고리즘

상어가 잡아먹은 물고기 번호의 최댓값을 구해야 합니다. 상어가 어떤 물고기부터 잡아먹었는지, 그 순서에 따라 뒤이어 잡아먹을 수 있는 물고기 조합이 달라질 수 있습니다. 따라서 2번째 물고기를 선택하여 최대한 많이 먹을 수 있을 때까지 재귀적으로 물고기와 상어를 이동시켜 보는 로직을 반복하고, 이 로직들에서 얻을 수 있는 물고기 섭취량의 최댓값을 정답으로 출력하면 됩니다. 개괄적인 문제해결 절차는 다음과 같습니다.

• 1) 상어는 좌표 내 물고기를 잡아먹고, 진행 방향은 잡아먹은 물고기의 진행 방향으로 변경
• 2) 모든 물고기 이동
  • 2-1) 물고기가 이동가능할 때까지 반시계 방향으로 45도씩 최대 한 바퀴까지 회전
  • 2-2) 진행 방향에 상어가 존재하지 않으면 해당 좌표로 1칸 이동
  • 2-3) 이동할 곳에 물고기가 존재하는 경우 해당 물고기와 위치 서로 교환(진행 방향 변화 X)
• 3) 잡아먹을 물고기 존재여부 확인
  • 3-1) 상어가 잡아먹을 물고기가 존재한다면 1) 과정부터 추가 진행
  • 3-2) 상어가 잡아먹을 물고기가 더 이상 존재하지 않는다면 함수를 종료하고 물고기 섭취량의 최댓값 출력

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline
import copy

# 물고기 좌표 찾는 함수
def find_fish(graph, fish):
    for i in range(N):
        for j in range(N):
            if graph[i][j][0] == fish:
                return (i, j)

# 모든 물고기 이동시키는 함수
def move_fish(x_shark, y_shark, graph):
    # 번호가 낮은 물고기부터 순차 이동
    for fish in range(1, 17):
        # 물고기 좌표 찾기
        position = find_fish(graph, fish)
        # 해당 물고기가 살아있는 경우
        if position:
            x_fish, y_fish = position[0], position[1] # 좌표 리턴받기
            direction = graph[x_fish][y_fish][1]
            # 반시계 방향으로 45도씩 최대 360도(1바퀴)까지 회전
            for _ in range(len(d)):
                # 해당 방향으로 진행
                nx_fish = x_fish + d[direction][0]
                ny_fish = y_fish + d[direction][1]
                # 맵 내부 위치한 경우
                if 0 <= nx_fish < N and 0 <= ny_fish < N:
                    # 진행할 곳에 상어가 없는 경우
                    if not (nx_fish == x_shark and ny_fish == y_shark):
                        # 해당 방향을 진행방향으로 확정
                        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(d)

# 상어의 이동가능한 좌표 찾는 함수
def get_movable_position(x_shark, y_shark, graph):
    direction = graph[x_shark][y_shark][1] # 상어 진행방향
    position = []
    # 최대 (맵 크기 -1)까지 이동 가능
    for _ in range(N-1):
        # 진행방향으로 전진
        x_shark += d[direction][0]
        y_shark += d[direction][1]
        # 진행 후 맵 내부에 위치해 있으며 물고기가 존재하는 경우
        if 0 <= x_shark < N and 0 <= y_shark < N and graph[x_shark][y_shark][0] != -1:
            position.append((x_shark, y_shark))
    return position

# 물고기를 모두 먹을 때까지 물고기와 상어를 이동시키는 재귀함수
def dfs(x_shark, y_shark, eat, graph):
    global answer
    graph = copy.deepcopy(graph)
    # 상어가 해당 물고기 잡아먹음
    eat += graph[x_shark][y_shark][0]
    graph[x_shark][y_shark][0] = -1 # 해당 위치 물고기 잡아먹힘 표시
    move_fish(x_shark, y_shark, graph) # 모든 물고기 이동
    # 상어의 이동가능한 좌표(=물고기 위치) 리턴받기
    position = get_movable_position(x_shark, y_shark, graph)

    # 이동가능한 좌표가 남은 경우
    if position:
        for nx_shark, ny_shark in position:
            dfs(nx_shark, ny_shark, eat, graph)
    else:
        answer = max(answer, eat)
        return

if __name__ == '__main__':
    N = 4
    graph = [[None]*N for _ in range(N)]
    for i in range(N):
        data = list(map(int, input().split()))
        for j in range(N):
            # 물고기 번호, 방향 정보 저장
            # 방향 정보 값에 1을 뺀 이유: 진행방향을 저장한 리스트(d)의 값이 인덱스 0부터 시작하기 떄문
            graph[i][j] = [data[2*j], data[2*j+1]-1]

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

2) 해설

(1) 패키지 import

import sys; input = sys.stdin.readline
import copy

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline 사용

• copy 모듈
  • 맵 정보를 깊은 복사(Deep Copy)하여 상어가 어떤 물고기부터 먹기 시작하느냐에 따른 모든 경우의 수를 연산하기 위해 사용
  • Deep Copy는 복사된 데이터 변경 시에도 원본 데이터 변경 방지

(2) 메인 함수

if __name__ == '__main__':
    N = 4
    graph = [[None]*N for _ in range(N)]
    for i in range(N):
        data = list(map(int, input().split()))
        for j in range(N):
            # 물고기 번호, 방향 정보 저장
            # 방향 정보 값에 1을 뺀 이유: 진행방향을 저장한 리스트(d)의 값이 인덱스 0부터 시작하기 떄문
            graph[i][j] = [data[2*j], data[2*j+1]-1]

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

• 맵의 크기(N)
  • 맵의 크기가 \(4\)로 주어졌지만 하드코딩을 최대한 지양하기 위해 변수 \(N\)에 맵의 크기 저장
• 맵 정보(graph)
  • 물고기 좌표마다 [번호, 방향] 저장
  • 방향 정보 값에서 \(1\)을 뺀 이유는 \(45\)도부터 \(360\)도까지의 방향 정보를 저장한 리스트(d)의 값이 인덱스 \(0\)부터 시작하는 것을 고려하기 위함

(3) DFS 함수

# 물고기를 모두 먹을 때까지 물고기와 상어를 이동시키는 재귀함수
def dfs(x_shark, y_shark, eat, graph):
    global answer
    graph = copy.deepcopy(graph)
    # 상어가 해당 물고기 잡아먹음
    eat += graph[x_shark][y_shark][0]
    graph[x_shark][y_shark][0] = -1 # 해당 위치 물고기 잡아먹힘 표시
    move_fish(x_shark, y_shark, graph) # 모든 물고기 이동
    # 상어의 이동가능한 좌표(=물고기 위치) 리턴받기
    position = get_movable_position(x_shark, y_shark, graph)

    # 이동가능한 좌표가 남은 경우
    if position:
        for nx_shark, ny_shark in position:
            dfs(nx_shark, ny_shark, eat, graph)
    else:
        answer = max(answer, eat)
        return

• 맵 정보(graph) deepcopy
  • 상어가 어떤 물고기부터 먹을지에 따라 결괏값이 달라지기 때문에 모든 경우의 수를 고려하기 위해 물고기 정보 deepcopy

(4) 물고기 이동시키는 함수

# 모든 물고기 이동시키는 함수
def move_fish(x_shark, y_shark, graph):
    # 번호가 낮은 물고기부터 순차 이동
    for fish in range(1, 17):
        # 물고기 좌표 찾기
        position = find_fish(graph, fish)
        # 해당 물고기가 살아있는 경우
        if position:
            x_fish, y_fish = position[0], position[1] # 좌표 리턴받기
            direction = graph[x_fish][y_fish][1]
            # 반시계 방향으로 45도씩 최대 360도(1바퀴)까지 회전
            for _ in range(len(d)):
                # 해당 방향으로 진행
                nx_fish = x_fish + d[direction][0]
                ny_fish = y_fish + d[direction][1]
                # 맵 내부 위치한 경우
                if 0 <= nx_fish < N and 0 <= ny_fish < N:
                    # 진행할 곳에 상어가 없는 경우
                    if not (nx_fish == x_shark and ny_fish == y_shark):
                        # 해당 방향을 진행방향으로 확정
                        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(d)

번호가 낮은 물고기부터 물고기를 이동시킵니다. 물고기가 진행할 수 있는 방향을 찾을 때까지 반시계 방향으로 \(45\)도씩 최대 \(360\)도까지 회전시킵니다.

(5) 물고기 좌표 찾는 함수

# 물고기 좌표 찾는 함수
def find_fish(graph, fish):
    for i in range(N):
        for j in range(N):
            if graph[i][j][0] == fish:
                return (i, j)

물고기 좌표를 반환하는 함수입니다.

(6) 상어의 이동가능한 좌표 찾는 함수

# 상어의 이동가능한 좌표 찾는 함수
def get_movable_position(x_shark, y_shark, graph):
    direction = graph[x_shark][y_shark][1] # 상어 진행방향
    position = []
    # 최대 (맵 크기 -1)까지 이동 가능
    for _ in range(N-1):
        # 진행방향으로 전진
        x_shark += d[direction][0]
        y_shark += d[direction][1]
        # 진행 후 맵 내부에 위치해 있으며 물고기가 존재하는 경우
        if 0 <= x_shark < N and 0 <= y_shark < N and graph[x_shark][y_shark][0] != -1:
            position.append((x_shark, y_shark))
    return position

상어가 현재 진행 방향으로 최대 (맵 크기\(-1\))까지 한 칸씩 이동하며 현재 위치에서 이동 가능한 모든 좌표를 리턴하는 함수입니다.

✅ 채점 결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_19236.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

 

📚 참고할 만한 포스팅

문제 풀이에 사용한 DFS 알고리즘에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/55

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.