Chap 19. 삼성전자 기출문제 - Q46. 아기 상어

@mildsalmon·

0

0

1. 아기 상어

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패)

from collections import deque

n = int(input())

space = []
fish = []
shark = []
shark_size = 2
shark_eat = 0

for i in range(n):
    temp = list(map(int, input().split()))
    space.append(temp)

    for j in range(n):
        if temp[j] != 0 and temp[j] != 9:
            fish.append((temp[j], i, j))
        elif temp[j] == 9:
            shark = [i, j]

fish.sort()

q = deque()

for i in range(len(fish)):
    if shark_size > fish[i][0]:
        temp = fish[i]
        q.append(temp)

time = 0

def dfs(space, temp_space, shark_x, shark_y, fish_x, fish_y, shark_size, time, result):
    ds = ((1, 0), (-1, 0), (0, 1), (0, -1))

    for d in ds:
        shark_dx = shark_x + d[0]
        shark_dy = shark_y + d[1]

        dist_temp = abs(shark_dx - fish_x) + abs(shark_dy - fish_y)

        if 0 <= shark_dx < len(space) and 0 <= shark_dy < len(space):
            if space[shark_dx][shark_dy] <= shark_size:
                if not temp_space[shark_dx][shark_dy]:
                    time += 1
                    # print(*space, sep='\n')
                    # print()
                    # print(*temp_space, sep='\n')
                    # print()
                    if fish_x == shark_dx and fish_y == shark_dy:
                        result.append(time)
                        # print(time)
                        # space[shark_dx][shark_dy]
                        temp_space[shark_dx][shark_dy] = False
                        break
                    else:
                        space[shark_dx][shark_dy] = 9  ###
                        temp_space[shark_dx][shark_dy] = True
                        dfs(space, temp_space, shark_dx, shark_dy, fish_x, fish_y, shark_size, time, result)
                        temp_space[shark_dx][shark_dy] = False
                        space[shark_dx][shark_dy] = 0
                        time -= 1
    # print("----")
    # return time

def bfs(temp_space, shark_x, shark_y, fish_x, fish_y, shark_size, time):
    b_q = deque()
    b_q.append((shark_x, shark_y))

    ds = ((1, 0), (-1, 0), (0, 1), (0, -1))

    while b_q:
        x, y = b_q.popleft()

        for d in ds:
            dx = x + d[0]
            dy = y + d[1]

            if 0 <= dx < len(temp_space) and 0 <= dy < len(temp_space):
                if temp_space[dx][dy] <= shark_size:
                    temp_space[dx][dy] = temp_space[x][y] + 1  ###

                    if dx == fish_x and dy == fish_y:
                        return temp_space[fish_x][fish_y]
                    else:
                        # temp_space[dx][dy] = time
                        b_q.append((dx, dy))
                    print(*temp_space, sep='\n')
                    print()
                    print(dx, dy)

    return 0

while q:
    print("Q: ", q)
    print("eat: ", shark_eat)
    print("size: ", shark_size)
    print("shark: ", shark)
    print("time: ", time)
    print("============")
    fish_num, fish_x, fish_y = q.popleft()
    shark_x, shark_y = shark

    while shark_x != fish_x or shark_y != fish_y:
        temp_space = [i[:] for i in space]
        result = []
        visited = [[False] * len(space) for _ in space]
        # print(temp_space)
        visited[shark_x][shark_y] = True
        temp_space[shark_x][shark_y] = 0
        # dfs(temp_space, visited, shark_x, shark_y, fish_x, fish_y, shark_size, 0, result)
        distance = bfs(temp_space, shark_x, shark_y, fish_x, fish_y, shark_size, 0)

        space[shark_x][shark_y] = 0
        space[fish_x][fish_y] = 9
        # result.sort()
        # distance = result[0]
        shark_x = fish_x
        shark_y = fish_y
        # print(result)

    # distance = abs(shark_x - fish_x) + abs(shark_y - fish_y)
    # print(distance)
    time += distance
    shark[0], shark[1] = fish_x, fish_y
    shark_eat += 1

    if shark_eat == shark_size:
        fish.sort(key=lambda x:[x[2], x[1]])
        shark_size += 1
        shark_eat = 0
        new_fish = []

        for i in range(len(fish)):
            if shark_size-1 == fish[i][0]:
                temp = [abs(shark[0] - fish[i][1]) + abs(shark[1] - fish[i][2])] + list(fish[i])
                new_fish.append(temp)

        new_fish.sort(key=lambda x:x[0])

        for new in new_fish:
            q.append(new[1:])

print(time)
b. 😊 2차 시도 (성공)

from collections import deque



if __name__ == "__main__":
    n = int(input())
    space = []
    shark_eat = 0
    shark_size = 2

    for i in range(n):
        temp = list(map(int, input().split()))
        space.append(temp)

        for j in range(n):
            if temp[j] == 9:
                shark_pos = (i, j)

                space[i][j] = 0

    ds = ((0, 1), (0, -1), (1, 0), (-1, 0))
    time = 0
    check = True
    while check:
        q = deque()
        q.append(shark_pos)
        visited = [[-1] * n for i in range(n)]
        visited[shark_pos[0]][shark_pos[1]] = 0

        while q:
            x, y = q.popleft()

            for d in ds:
                dx = x + d[0]
                dy = y + d[1]

                if 0 <= dx < n and 0 <= dy < n:
                    if visited[dx][dy] == -1 and space[dx][dy] <= shark_size:
                        visited[dx][dy] = visited[x][y] + 1
                        q.append((dx, dy))

        fish = [7, 0, 0, 0, 1e9]
        # print(visited)
        is_fish = False
        dist = 1e9
        for i in range(n):
            for j in range(n):
                if visited[i][j] != -1 and 0 < space[i][j] < shark_size:
                    if visited[i][j] < dist:
                        dist = visited[i][j]
                        fish = [i, j, dist]
                        is_fish = True

        if is_fish:
            time += fish[2]
            shark_pos = (fish[0], fish[1])
            space[shark_pos[0]][shark_pos[1]] = 0

            shark_eat += 1

            if shark_eat == shark_size:
                shark_eat = 0
                shark_size += 1
        else:
            break
        # print(time)
        # print(*space, sep='\n')
        # print()

    print(time)
c. 😊 3차 시도 (성공 - 함수화)

from collections import deque

def search_minimum_distance(shark_pos, space):
    """
    상어가 모든 지점으로 가는 최단거리를 구함
    :param shark_pos: 상어 현재 위치
    :param space: 물고기 지도
    :return: 최단거리 지도
    """
    global n

    ds = ((0, 1), (0, -1), (1, 0), (-1, 0))

    x, y = shark_pos
    q = deque()
    q.append((x, y))
    visited = [[-1] * n for _ in range(n)]
    visited[x][y] = 0

    while q:
        x, y = q.popleft()

        for d in ds:
            dx = x + d[0]
            dy = y + d[1]

            if 0 <= dx < n and 0 <= dy < n:
                if visited[dx][dy] == -1 and space[dx][dy] <= shark_size:
                    visited[dx][dy] = visited[x][y] + 1
                    q.append((dx, dy))

    return visited

def find_fish(minimum_distance_map):
    """
    상어가 먹을 수 있는 크기의 물고기를 찾는다.
    만약, 동일한 크기의 물고기가 존재한다면, 우선순위를 (1. 위, 2. 왼쪽)로 정하고 물고기를 찾는다.
    :param minimum_distance_map: 상어에서 모든 물고기까지 가는 최단거리 지도
    :return:
    """
    global n

    dist = 1e9
    fish_x = 0
    fish_y = 0

    for i in range(n):
        for j in range(n):
            if minimum_distance_map[i][j] != -1 and 0 < space[i][j] < shark_size:
                if minimum_distance_map[i][j] < dist:
                    dist = minimum_distance_map[i][j]
                    fish_x = i
                    fish_y = j

    if dist != 1e9:
        fish = [dist, fish_x, fish_y]
        return fish
    else:
        return None

def eat_shark(eat, size):
    """
    상어가 물고기를 먹는 메소드
    먹은 물고기 수가 상어 크기와 같다면, 상어 크기가 1 커진다.
    :param eat:
    :param size:
    :return:
    """
    eat += 1

    if eat == size:
        eat = 0
        size += 1

    return eat, size

if __name__ == "__main__":
    n = int(input())
    space = []
    shark_eat = 0
    shark_size = 2

    for i in range(n):
        temp = list(map(int, input().split()))
        space.append(temp)

        for j in range(n):
            if temp[j] == 9:
                shark_pos = (i, j)

    time = 0

    while True:
        space[shark_pos[0]][shark_pos[1]] = 0

        minimum_distance_map = search_minimum_distance(shark_pos, space)
        fish = find_fish(minimum_distance_map)

        if fish is not None:
            time += fish[0]
            shark_pos = (fish[1], fish[2])
            shark_eat, shark_size = eat_shark(shark_eat, shark_size)
        else:
            break

    print(time)
d. 😊 4차 시도 (성공 - 클래스화)

"""
Date    : 2021.12.07
Update  : 2021.12.07
Source  : Q46_아기 상어.py
Purpose : bfs를 이용하여 구현하는 문제
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

from collections import deque

class Area:
    """
    공간에 대한 클래스
    """
    def __init__(self, n, space):
        self.n = n
        self.space = space
        self.shark_pos = self.get_shark_pos()
        self.ds = ((0, 1), (0, -1), (1, 0), (-1, 0))

    def get_minimum_distance(self, shark_size):
        """
        상어가 모든 지점으로 가는 최단거리를 구함
        :param shark_size: BabyShark 클래스에 있는 상어 크기
        :return: 최단거리 지도
        """
        x, y = self.shark_pos

        q = deque()
        q.append((x, y))
        distance_map = [[-1] * self.n for _ in range(self.n)]
        distance_map[x][y] = 0

        while q:
            x, y = q.popleft()

            for d in self.ds:
                dx = x + d[0]
                dy = y + d[1]

                if 0 <= dx < n and 0 <= dy < n:
                    if distance_map[dx][dy] == -1 and self.space[dx][dy] <= shark_size:
                        distance_map[dx][dy] = distance_map[x][y] + 1
                        q.append((dx, dy))

        return distance_map

    def get_shark_pos(self):
        """
        현재 상어 위치를 요청함.
        :return: 현재 상어 위치
        """
        for i in range(n):
            for j in range(n):
                if self.space[i][j] == 9:
                    self.shark_pos = (i, j)
        return self.shark_pos

    def update_shark_pos(self, x, y, value):
        """
        상어 위치를 업데이트함.
        :param x: 수정할 상어의 x좌표
        :param y: 수정할 상어의 y좌표
        :param value: 수정할 내용 / 0은 상어 지우기, 9는 상어 만들기
        :return:
        """
        self.space[x][y] = value

    def get_space(self):
        """
        현재 남은 물고기 지도를 요청함.
        :return: 물고기 지도
        """
        return self.space


class BabyShark:
    """
    상어에 대한 내용을 담은 클래스
    """
    def __init__(self, eat, size):
        self.eat = eat
        self.size = size

    def find_fish(self, minimum_distance_map, space):
        """
        상어가 먹을 수 있는 크기의 물고기를 찾는다.
        만약, 동일한 크기의 물고기가 존재한다면, 우선순위를 (1. 위, 2. 왼쪽)로 정하고 물고기를 찾는다.
        :param minimum_distance_map: 상어에서 모든 물고기까지 가는 최단거리 지도
        :param space: 물고기 지도
        :return:
        """
        n = len(minimum_distance_map)

        fish = [1e9, 0, 0]

        for i in range(n):
            for j in range(n):
                if minimum_distance_map[i][j] != -1 and 0 < space[i][j] < self.size:
                    if minimum_distance_map[i][j] < fish[0]:
                        fish[0] = minimum_distance_map[i][j]
                        fish[1] = i
                        fish[2] = j

        if fish[0] != 1e9:
            return fish
        else:
            return None

    def eat_shark(self):
        """
        상어가 물고기를 먹는 메소드
        먹은 물고기 수가 상어 크기와 같다면, 상어 크기가 1 커진다.
        :return:
        """
        self.eat += 1

        if self.eat == self.size:
            self.eat = 0
            self.size += 1

    def get_size(self):
        """
        현재 상어의 크기를 요청함.
        :return: 상어의 크기
        """
        return self.size

if __name__ == "__main__":
    n = int(input())
    space = []
    shark_eat = 0
    shark_size = 2

    for i in range(n):
        temp = list(map(int, input().split()))
        space.append(temp)

    time = 0

    area = Area(n, space)
    baby_shark = BabyShark(shark_eat, shark_size)

    while True:
        shark_pos = area.get_shark_pos()
        area.update_shark_pos(shark_pos[0], shark_pos[1], 0)

        minimum_distance_map = area.get_minimum_distance(baby_shark.get_size())
        fish = baby_shark.find_fish(minimum_distance_map, area.get_space())
        # print(fish)
        if fish is not None:
            time += fish[0]
            area.update_shark_pos(fish[1], fish[2], 9)
            baby_shark.eat_shark()
        else:
            break

    print(time)
e. 🙄 회고

내 풀이

  • 처음에는 못풀었다.
    • 물고기 순번을 정리했더니, 상어를 못찾겠더라..

결론

  • 자주 반복해야지..

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

  1. 현재 상어 위치에서 모든 위치에 대한 최단 거리를 구한다.
  2. 먹을 수 있는 물고기 중 우선순위에 따라 물고기 위치로 이동하여 먹는다.

큰 틀은 위 내용이 전부이다.

1번에서는 bfs를 사용해야하고, 2번에서는 최단거리 지도와 상어 크기를 통해 물고기를 선정해야한다.

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] baekjoon. 16236번: 아기 상어 (acmicpc.net). Baekjoon. (accessed Dec 7, 2021)

파이썬
알고리즘
한빛미디어
나동빈
코딩테스트
문제
풀이
구현
백준
bf

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.