[백준] 23290 : 마법사 상어와 복제 (삼성 SW 역량 테스트) / python

1. 문제 설명

23290번: 마법사 상어와 복제

오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. 
(r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.

격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다.
이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다.
상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

 

• 상어가 모든 물고기에게 복제 마법을 시전한다.
  복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
• 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다.
  각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 
  만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다.
  물고기의 냄새는 아래 3에서 설명한다.
• 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다.
  연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다.
  연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면,
  그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다.
  가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며,
  그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
• 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
• 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

 

격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다.
S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

 

2. 풀이 전 계획과 생각

위의 문제는 삼성에서 자주 출제되는 시뮬레이션 + 완전 탐색 문제다. 문제에서 제시된 순서에 맞게 코드를 짜면 된다.

필요한 자료구조는 다음과 같다.
물고기의 냄새를 기록해주는 배열, 물고기의 현재 상태 배열, 물고기의 다음 상태 배열, 물고기 상태 값을 복사한 배열이 필요하다.
상태 배열에는 물고기의 방향을 저장해주었다.

 

1. 상어의 물고기에게 복제 마법을 시전하는 함수
   현재 상태 배열에는 물고기의 방향 값이 들어있는데, 이를 복사하여 임시 배열(물고기 상태 값을 복사한 배열)에 넣어준다.
2. 모든 물고기가 한 칸씩 이동하는 함수
   각 격자의 칸을 완전탐색하여 물고기 방향을 꺼내 이동시킨다.
   이동할 수 있는 경우는 이동하는 좌표가 상어의 좌표와 달라야하고, 냄새가 없어야 하며, 범위에 있어야 한다.
   자신이 이동할 수 있는 칸을 향할 때까지 45도 반시계 방향으로 회전시킨다.
   반시계 방향 회전은 (cur_dir - delta) % FISH_DIR_NUM으로 해주면 된다.
   동시에 이동하므로 다음 상태 배열에 물고기 상태 값을 넣어주고, 다음 상태 배열의 값은 현재 상태 배열에 넣는다.
3. 상어가 연속해서 세 칸씩 이동하는 함수
   상어가 움직이는 함수다.
   상어가 이동하면서 최대한 많은 물고기를 먹어야 하는 문제이기에 모든 경우를 다 따져주어야 한다.
   모든 경우를 다 따지기 위해서, 방향이 (0, 0, 0) ~ (3, 3, 3) 설정하여 사전순으로 탐색하도록 한다.
   이를 위해 3중 반복문을 사용하여 모든 경우를 따진다.
   
   각 경우마다 물고기 횟수를 세어주어야 한다.
   이때 상어가 이미 지나간 자리를 또 지나갈 수 있게 되는데 이때는 물고기 횟수를 더해주면 안되므로
   visit 해시셋을 생성하여 이미 지나간 자리인지 판단해주어야 한다.
   
   지나간 부분의 물고기의 냄새를 기록하는 배열은 3으로 초기화 해주어야 한다.
   이 배열은 턴을 돌면서 1씩 줄어들며 냄새가 희미해진다.
4. 두번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라지게 하는 함수
   물고기의 냄새를 기록해주는 배열의 값을 1씩 줄어들게하여 냄새가 희미해지게 한다.
5. 1에서 사용한 복제마법이 완료되는 함수
   물고기 상태 값을 복사한 임시 배열에서 원소들을 꺼내 현재 상태 배열에 추가한다.

 

3. 풀이

def init():
    m, s = tuple(map(int, input().split()))
    input_grid = [
        [[] for _ in range(N)]
        for _ in range(N)
    ]

    for _ in range(m):
        fish_r, fish_c, fish_dir = tuple(map(int, input().split()))
        fish_r, fish_c, fish_dir = fish_r - 1, fish_c - 1, fish_dir - 1
        input_grid[fish_r][fish_c].append(fish_dir)

    sr, sc = tuple(map(int, input().split()))
    sr, sc = sr - 1, sc - 1

    return m, s, input_grid, sr, sc

def magic_copy():
    copy_fish = [
        [[] for _ in range(N)]
        for _ in range(N)
    ]

    for i in range(N):
        for j in range(N):
            for element in grid[i][j]:
                copy_fish[i][j].append(element)

    return copy_fish

def in_range(r, c):
    return 0 <= r < N and 0 <= c < N

def get_next(cur_r, cur_c, cur_dir):
    # ←, ↖, ↑, ↗, →, ↘, ↓, ↙
    drs = [0,  -1, -1, -1, 0, 1, 1,  1]
    dcs = [-1, -1,  0,  1, 1, 1, 0, -1]

    for delta in range(FISH_DIR_NUM):
        next_dir = (cur_dir - delta) % FISH_DIR_NUM
        next_r, next_c = cur_r + drs[next_dir], cur_c + dcs[next_dir]
        if in_range(next_r, next_c):
            if (next_r, next_c) != (shark_r, shark_c) and smell[next_r][next_c] == 0:
                return next_r, next_c, next_dir
    return cur_r, cur_c, cur_dir

def move_fish():
    next_grid = [
        [[] for _ in range(N)]
        for _ in range(N)
    ]

    for i in range(N):
        for j in range(N):
            for element in grid[i][j]:
                next_i, next_j, next_dir = get_next(i, j, element)
                next_grid[next_i][next_j].append(next_dir)

    for i in range(N):
        for j in range(N):
            grid[i][j] = next_grid[i][j]

def get_fish_num(dir1, dir2, dir3):
    dr = [-1, 0, 1, 0]
    dc = [0, -1, 0, 1]

    r, c = shark_r, shark_c
    predicted_fish_num = 0

    # 방문한 적이 있는지를 기록
    visited_position = set()

    for move_dir in [dir1, dir2, dir3]:
        next_r, next_c = r + dr[move_dir], c + dc[move_dir]

        # 움직이는 도중에 격자를 벗어나면 선택되면 안된다.
        if not in_range(next_r, next_c):
            return -1

        # 이미 계산한 곳에 대해서는 중복 계산하지 않는다.
        if (next_r, next_c) not in visited_position:
            predicted_fish_num += len(grid[next_r][next_c])
            visited_position.add((next_r, next_c))

        r, c = next_r, next_c

    return predicted_fish_num

def move_shark():
    dr = [-1, 0, 1, 0]
    dc = [0, -1, 0, 1]

    max_count = -1
    best_route = (-1, -1, -1)

    for i in range(SHARK_DIR_NUM):
        for j in range(SHARK_DIR_NUM):
            for k in range(SHARK_DIR_NUM):
                current_count = get_fish_num(i, j, k)
                if current_count > max_count:
                    max_count = current_count
                    best_route = (i, j, k)

    global shark_r, shark_c
    dir1, dir2, dir3 = best_route
    for move_dir in [dir1, dir2, dir3]:
        next_r, next_c = shark_r + dr[move_dir], shark_c + dc[move_dir]
        # 물고기가 존재하면, 물고기를 격자에서 제외하고 냄새를 남긴다.
        if len(grid[next_r][next_c]) > 0:
            smell[next_r][next_c] = 3
            grid[next_r][next_c] = list()
        shark_r, shark_c = next_r, next_c

def disappear_smell():
    for i in range(N):
        for j in range(N):
            if smell[i][j] > 0:
                smell[i][j] -= 1

def complete_copy(copy_fish):
    for i in range(N):
        for j in range(N):
            for element in copy_fish[i][j]:
                grid[i][j].append(element)

def simulate():
    copy_fish = magic_copy()
    # print("step1")
    # print_grid()
    # print(shark_r, shark_c)
    move_fish()
    # print("step2")
    # print_grid()
    # print(shark_r, shark_c)
    move_shark()
    # print("step3")
    # print_grid()
    # print(shark_r, shark_c)
    disappear_smell()
    # print("step4")
    # print_smell()
    # print(shark_r, shark_c)
    complete_copy(copy_fish)
    # print("step5")
    # print_grid()
    # print(shark_r, shark_c)

def pro():
    for _ in range(S):
        simulate()

def print_answer():
    count = 0
    for i in range(N):
        for j in range(N):
            for _ in grid[i][j]:
                count += 1
    print(count)

def print_grid():
    for i in range(N):
        for j in range(N):
            print(grid[i][j], end=" ")
        print()

def print_smell():
    for i in range(N):
        for j in range(N):
            print(smell[i][j], end=" ")
        print()

N = 4
FISH_DIR_NUM = 8
SHARK_DIR_NUM = 4

smell = [[0] * N for _ in range(N)]
M, S, grid, shark_r, shark_c = init()
pro()
print_answer()

 

4. 풀이 후 알게된 개념과 소감

👻 실수 및 예외 케이스

• 연속해서 3칸 이동할 때 같은 위치에 또 올 수 있다는 것을 고려해주지 못했다.
  상어가 같은 위치에 올 수 있기에 중복 계산을 막기 위해 방문 처리를 해준다.
• 상어가 이동할 때, 물고기가 있을 때, 빈격자와 냄새를 남겨야 하는데 상어가 이동하는 모든 칸에다가 빈격자를 만들고 냄새를 남겼다.
• 이 문제는 물고기만 격자에 넣어주고 상어는 좌표만 나타내주면 된다.
• 반시계 방향 회전인데 시계 방향 회전을 해주었다.

⭐️ 실제 처리가 아닌 카운팅 해줄 때, 중복 계산을 막아주는 것을 잊지 말자! ⭐️