Chap 19. 삼성전자 기출문제 - Q47. 청소년 상어

@mildsalmon·2021-12-13 11:31

1. 청소년 상어

난이도
- 골드 2
풀이 시간
- 50분
시간 제한
- 1초
메모리 제한
- 512MB
출처
- 19236번: 청소년 상어 (acmicpc.net)

A. 📜 문제

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

B. 💡 내 답안

a. 😅 1차 시도 (실패)


from collections import deque
import copy

# def bfs(x, y):
#     new_q = deque()
#     # 방향 좌표 먹은거 반환
#     d = ds[fishs[x][y][1]]
#     dx = x + d[0]
#     dy = y + d[1]
#
#     if 0 <= dx < n and 0 <= dy < n:
#         if fishs[dx][dy][0] != 0 and fishs[dx][dy][0] != 99:
def bfs(array, x, y):
    q = deque()
    # shark_eat = 0

    # shark_move = [0, 0, 0, 0]
    for i in range(1, n):
        d = ds[fishs[x][y][1]]
        dx = x + d[0] * i
        dy = y + d[1] * i

        if 0 <= dx < n and 0 <= dy < n:
            # 물고기가 없는칸 제외
            if fishs[dx][dy][0] != 0 and fishs[dx][dy][0] != 99:
                q.append((dx, dy))
        else:
            break

    if len(q) == 0:
        # 상어가 지금까지 먹은 먹이 합
        next_fish = [fishs[x][y][0], x, y, fishs[x][y][1]]
        # eat_fish = [x, y]

        return next_fish #, eat_fish

    next_fishs = []
    eat_fishs = []
    # temp_fishs = []

    while q:
        nx, ny = q.popleft()
        next_fish = bfs(nx, ny)

        next_fishs.append(next_fish)
        # temp_fishs.append(eat_fish)

    next_fish = next_fishs[0]

    for i in range(1, len(next_fishs)):
        if next_fishs[i][0] > next_fishs[i-1][0]:
            next_fish = next_fishs[i]

    next_fish[0] += fishs[x][y][0]
    fishs[next_fish[1]][next_fish[2]][0] = 0
    next_fish[1] = x
    next_fish[2] = y
    # eat_fishs.append(next_fish)

    return next_fish#, eat_fishs

n = 4

fishs = []

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

    fish = []
    for j in range(n):
        fish.append([temp[j*2], temp[j*2+1]-1])
    fishs.append(fish)

ds = ((-1, 0), # 상
      (-1, -1), # 대 (왼상)
      (0, -1), # 왼
      (1, -1), # 대 (왼하)
      (1, 0), # 하
      (1, 1), # 대 (오하)
      (0, 1), # 오
      (-1, 1)) # 대 (오상)

ds_len = len(ds)

shark_pos = (0, 0)
shark_direction = fishs[0][0][1]
shark_eat = 0
shark_eat += fishs[0][0][0]

while True:
    fishs[0][0][0] = 99 # 상어

    # 물고기 이동
    moved_fish = [False] * (n*n + 1)

    for k in range(1, n*n+1):
        for i in range(n):
            for j in range(n):
                if fishs[i][j][0] == k and not moved_fish[k]:
                    for dk in range(ds_len):
                        d = ds[(fishs[i][j][1] + dk) % ds_len]
                        dx = i + d[0]
                        dy = j + d[1]

                        if 0 <= dx < n and 0 <= dy < n:
                            if fishs[dx][dy][0] != 99:
                                fishs[i][j][1] = (fishs[i][j][1] + dk) % ds_len
                                fishs[i][j], fishs[dx][dy] = fishs[dx][dy], fishs[i][j]
                                moved_fish[k] = True
                                break

    # 상어 이동
    fishs[shark_pos[0]][shark_pos[1]][0] = 0  # 상어 이동 준비
    next_fish = bfs(shark_pos[0], shark_pos[1])
    fishs[shark_pos[0]][shark_pos[1]][1] = next_fish[3]
    # print(next_fish)
    shark_eat += next_fish[0]

    if next_fish[0] == 0 or (next_fish[1] == 0 and next_fish[2] == 0):
        print(shark_eat)
        break
    # q = deque()
    #
    # # shark_move = [0, 0, 0, 0]
    # for i in range(n):
    #     d = ds[shark_direction]
    #     dx = shark_pos[0] + d[0] * i
    #     dy = shark_pos[1] + d[1] * i
    #
    #     if 0 <= dx < n and 0 <= dy < n:
    #         # 물고기가 없는칸 제외
    #         if fishs[dx][dy][0] != 0 and fishs[dx][dy][0] != 99:
    #             q.append((dx, dy))
    #     else:
    #         break
    #
    # while q:
    #     x, y = q.popleft()
    #     bfs(x, y)
                # shark_move = max(shark_move, [fishs[dx][dy][0], fishs[dx][dy][1], dx, dy])
    # shark_eat += shark_move[0]
    # shark_pos = (shark_move[2], shark_move[3])
    # shark_direction = shark_move[1]

b. 😊 2차 시도 (성공)


import copy

def fish_move(fishs):
    """
    물고기 이동 코드
    :param fishs:
    :return:
    """
    fish_moved = [False] * (n*n+1)

    for k in range(1, n * n + 1):
        for i in range(n):
            for j in range(n):
                if fishs[i][j][0] == k and not fish_moved[k]:
                    for dk in range(len(ds)):
                        next_pos = (fishs[i][j][1] + dk)%len(ds)
                        d = ds[next_pos]
                        dx = i + d[0]
                        dy = j + d[1]

                        if 0 <= dx < n and 0 <= dy < n:
                            if fishs[dx][dy][0] != 99:
                                fishs[i][j][1] = next_pos
                                fishs[i][j], fishs[dx][dy] = fishs[dx][dy], fishs[i][j]
                                fish_moved[k] = True
                                # print(*fishs, sep='\n')
                                # print()
                                break

def dfs(x, y, shark_eat, shark_direction, fishs):
    """
    상어 이동 코드드
   :param x:
    :param y:
    :param shark_eat:
    :param shark_direction:
    :param fishs:
    :return:
    """
    copy_fish = copy.deepcopy(fishs)
    shark_eat += copy_fish[x][y][0]
    copy_fish[x][y][0] = 99
    fish_move(copy_fish)
    eat_list = []
    shark_eat_list = []

    for i in range(1, n):
        next_pos = (shark_direction)
        d = ds[next_pos]
        dx = x + d[0] * i
        dy = y + d[1] * i

        if 0 <= dx < n and 0 <= dy < n:
            if copy_fish[dx][dy][0] != -1:
                eat_list.append((dx, dy))

    copy_fish[x][y][0] = -1

    if len(eat_list) == 0:
        return shark_eat

    for eat in eat_list:
        shark_direction = copy_fish[eat[0]][eat[1]][1]
        shark_eat_list.append(dfs(eat[0], eat[1], shark_eat, shark_direction, copy_fish))

    return max(shark_eat_list)


if __name__ == "__main__":
    n = 4

    fishs = []

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

        fish = []
        for j in range(n):
            fish.append([temp[j*2], temp[j*2+1]-1])
        fishs.append(fish)

    ds = ((-1, 0), # 상
          (-1, -1), # 대 (왼상)
          (0, -1), # 왼
          (1, -1), # 대 (왼하)
          (1, 0), # 하
          (1, 1), # 대 (오하)
          (0, 1), # 오
          (-1, 1)) # 대 (오상)

    ds_len = len(ds)

    shark_pos = (0, 0)
    shark_direction = fishs[0][0][1]
    shark_eat = 0
    # shark_eat += fishs[0][0][0]

    shark_eat = dfs(shark_pos[0], shark_pos[1], shark_eat, shark_direction, fishs)

    # print(*fishs, sep='\n')
    print(shark_eat)

c. 😊 2차 시도 (성공 - 클래스로 리팩토링)


"""
Date    : 2021.12.09
Update  : 2021.12.13
Source  : Q46_아기 상어.py
Purpose : dfs로 구현한 것을 클래스로 변경함.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

import copy

class Fish:
    """
    물고기
    """
    def __init__(self, num, direction):
        """
        물고기 번호와 방향을 생성자의 매개변수로 받음
        :param num:
        :param direction:
        """
        self.num = num
        self.direction = direction

    def get_info(self) -> list:
        """
        물고기 전체 정보 반환
        처음에는 get_num, get_direction 메소드를 따로 만들기 번거로워서 만들었는데,
        num 정보만 필요할 경우 이 메소드는 [num, direction]을 반환하므로 더 복잡해져서 잘 안쓰게 되었다.
        :return: [물고기 번호, 물고기 방향]
        """
        return [self.num, self.direction]

    def set_direction(self, new_direction):
        """
        물고기는 현재 방향으로 이동하지 못한다면, 최대 한 바퀴동안 방향을 45도 변경하며 탐색한다.
        이때, 물고기의 방향값이 수정되어야 한다.
        :param new_direction:
        :return:
        """
        self.direction = new_direction

    def get_direction(self) -> int:
        """
        물고기 방향 반환
        :return:
        """
        return self.direction

    def get_num(self) -> int:
        """
        물고기 번호 반환
        :return:
        """
        return self.num

    def set_num(self, num):
        """
        상어가 물고기를 먹었다면, 물고기 번호를 지우거나 (-1), 상어(99)로 바꿔줘야 한다
        :param num:
        :return:
        """
        self.num = num

class Shark:
    """
    상어
    """
    def __init__(self, pos, direction, eat):
        """
        :param pos: 초기 좌표 튜플
        :param direction: 방향
        :param eat: 먹은 물고기 번호 합
        """
        self.pos = pos
        self.direction = direction
        self.eat = eat

    def change_direction(self, new_direction):
        """
        상어 방향을 바꿈
        dfs 매개변수로 상어 방향을 바로 입력해주어서 사용하지는 않음.
        :param new_direction:
        :return:
        """
        self.direction = new_direction

    def get_info(self) -> list:
        """
        상어 정보를 반환
        :return:
        """
        return [self.pos, self.direction, self.eat]

    def change_eat(self, eat):
        """
        상어가 먹은 물고기 수를 갱신
        :param eat:
        :return:
        """
        self.eat = eat

    def get_eat(self) -> int:
        """
        현재까지 먹은 물고기 수를 반환
        :return:
        """
        return self.eat

class Area:
    """
    맵과 관련된 클래스
    맵의 이동, 상어 이동 포함.
    """
    def __init__(self):
        self.ds = ((-1, 0), # 상
              (-1, -1), # 대 (왼상)
              (0, -1), # 왼
              (1, -1), # 대 (왼하)
              (1, 0), # 하
              (1, 1), # 대 (오하)
              (0, 1), # 오
              (-1, 1)) # 대 (오상)
        self.n = 4
        self.game_map = [[None] * self.n for _ in range(self.n)]

    def set_fish(self, x, y, fish):
        """
        맵에 물고기를 저장
        :param x: x좌표
        :param y: y좌표
        :param fish: Fish 객체
        :return:
        """
        self.game_map[x][y] = fish

    def show_map(self):
        """
        간단하게 맵에 위치한 물고기 정보를 확인할 수 있게함.
        :return:
        """
        for i in range(self.n):
            for j in range(self.n):
                print(self.game_map[i][j].get_info(), end=' ')
            print()

    def move(self, game_map):
        """
        상어가 한 번 움직이면, 물고기가 이동해야함.
        dfs를 활용해서, Area 클래스의 인스턴스 객체를 활용하지 않고 매개변수 값을 활용함.
        :param game_map: 이전 물고기들의 움직임이 저장된 지도
        :return:
        """
        fish_moved = [False] * (self.n * self.n + 1)

        for k in range(1, self.n * self.n + 1):
            for i in range(self.n):
                for j in range(self.n):
                    if game_map[i][j].get_num() == k and not fish_moved[k]:
                        for dk in range(len(self.ds)):
                            next_pos = (game_map[i][j].get_direction() + dk) % len(self.ds)
                            d = self.ds[next_pos]
                            dx = i + d[0]
                            dy = j + d[1]

                            if 0 <= dx < self.n and 0 <= dy < self.n:
                                if game_map[dx][dy].get_num() != 99:
                                    game_map[i][j].set_direction(next_pos)
                                    game_map[i][j], game_map[dx][dy] = game_map[dx][dy], game_map[i][j]
                                    fish_moved[k] = True
                                    # print(*fishs, sep='\n')
                                    # print()
                                    break

    def get_map(self) -> list:
        """
        현재 지도에 저장된 물고기 정보를 반환
        처음 1회만 사용됨.
        :return:
        """
        return self.game_map

    def dfs(self, x, y, shark_eat, shark_direction, copy_map):
        """
        상어 이동 코드
        어느 클래스에 포함시켜야할지 고민이었다. 차라리 클래스 밖에 함수로 존재시키는 것이 더 좋았을지도 모르겠다.
        이 함수에서는 인자로 전달해준 값을 갱신하여 비교를 진행하므로 인스턴스 변수의 사용이 불필요하다.
        :param x:
        :param y:
        :param shark_eat:
        :param shark_direction:
        :param copy_map:
        :return:
        """
        new_copy_map = copy.deepcopy(copy_map)
        shark_eat += new_copy_map[x][y].get_num()
        new_copy_map[x][y].set_num(99)
        self.move(new_copy_map)
        eat_list = []
        shark_eat_list = []

        for i in range(1, self.n):
            next_pos = shark_direction
            d = self.ds[next_pos]
            dx = x + d[0] * i
            dy = y + d[1] * i

            if 0 <= dx < self.n and 0 <= dy < self.n:
                if new_copy_map[dx][dy].get_num() != -1:
                    eat_list.append((dx, dy))

        new_copy_map[x][y].set_num(-1)

        if len(eat_list) == 0:
            return shark_eat

        for eat in eat_list:
            shark_direction = new_copy_map[eat[0]][eat[1]].get_direction()
            shark_eat_list.append(self.dfs(eat[0], eat[1], shark_eat, shark_direction, new_copy_map))

        return max(shark_eat_list)


if __name__ == "__main__":
    area = Area()

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

        for j in range(area.n):
            fish = Fish(temp[j*2], temp[j*2+1]-1)
            area.set_fish(i, j, fish)

    # area.show_map()

    shark = Shark((0,0), area.game_map[0][0].get_direction(), 0)

    # print(shark.get_info())
    shark_info = shark.get_info()

    shark.change_eat(area.dfs(shark_info[0][0], shark_info[0][1], shark_info[2], shark_info[1], area.get_map()))

    print(shark.get_eat())

d. 🙄 회고

내 풀이

처음에는 bfs로 잘못 접근해서 많이 돌아갔다.
클래스로 리팩토링할때도, 이게 맞는건가 싶은 부분들이 많았다.

C. 🧐 문제 해설

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

# 물고기는 번호와 방향을 갖는다.
    # 방향을 45도 반시계로

# 초기

# 상어는 물고기를 먹고 물고기 방향으로 이동한다.
    # 물고기 먹고 빈칸 만들기

# 물고기도 움직임
    # 이동 x -> 상어가 있거나, 공간 밖
    # 번호가 작은 순서로 이동함.
    # 이동할 수 있을떄까지 45도 회전
        # 회전한 방향으로 물고기의 방향을 갱신해야함.
    #이동 x면 이동 x
    # 다른 물고기칸으로 이동할때는 서로 위치를 바꾸는 방식으로

# 물고기 이동 -> 상어 이동

# 상어
    # 방향에 있는 칸을 이동할 수 있고 한 번에 여러 칸을 이동할 수 있음
        # 한 턴에 한번만 물고기를 먹을 수 있음
    # 물고기가 있는칸으로 이동하면, 물고기 먹고 물고기의 방향을 갖는다.
    # 지나가는 칸에 있는 물고기는 먹지 않음
    # 빈 칸으로는 이동하지 못함
        # 이동하던 중 칸이 없으면 집으로 돌아감 ==> 이거를 초기 시작위치인 0,0으로 돌아간다고 이해하고 풀었음

# 상어가 집으로 가면 게임이 끝남.

위 조건들을 만족하게 하면서 구현하면 된다.