[Python/Codetree] 메두사와 전사들

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/medusa-and-warriors/description

코딩테스트 기출 문제 설명: 메두사와 전사들 | 코드트리

문제

$0$ 에서 $N-1$의 범위로 이루어진 $ N \times N$ 크기의 어느 마을에 메두사가 살고 있습니다. 

이 마을에는 도로가 깔려 있으며, 도로는 0, 도로가 아닌 곳은 1로 주어집니다.

메두사는 집에서 공원까지 산책을 나가기로 했습니다. 

메두사의 집은 좌표 $(S_{r}, S_{c})$ 에 있고, 공원은 좌표 $(E_{r}, E_{c})$ 에 위치해 있습니다.

메두사는 오직 도로만을 따라 최단 경로로 공원까지 이동합니다. 이때 메두사의 집과 공원은 항상 도로위에 있으며, 집과 공원의 좌표는 다름을 가정해도 좋습니다. 

그런데 오늘은 $M$ 명의 용감한 전사들이 메두사를 잡기 위해 마을에 도착했습니다. 

각 전사는 초기에 $(r_{i}, c_{i})$ 에 위치해있으며, 메두사를 향해 최단 경로로 이동합니다. 전사들은 도로와 비도로를 구분하지 않고 어느 칸이든 이동할 수 있습니다. 메두사의 집에 전사들이 초기부터 위치하는 경우 또한 없음을 가정해도 좋습니다. 

전사들이 마을에 들어와있음을 미리 알고 있던 메두사는 전사들이 움직이기 전에 그들을 바라봄으로써 돌로 만들어 움직임을 멈출 수 있습니다.

메두사와 전사들의 이동은 매턴마다 다음 순서에 맞춰 차례로 진행됩니다.

 

 [1] 메두사의 이동 

메두사는 도로를 따라 한 칸 이동하며, 공원까지 최단 경로를 따릅니다. 메두사가 이동한 칸에 전사가 있을 경우 전사는 메두사에게 공격을 받고 사라집니다. 만약 집으로부터 공원까지 여러 최단경로가 가능하다면 상, 하, 좌, 우의 우선순위를 따릅니다. 또한 메두사의 집으로부터 공원까지 도달하는 경로가 없을 수도 있음을 유의하세요.

 

[2] 메두사의 시선

메두사는 상, 하, 좌, 우 하나의 방향을 선택해 바라봅니다. 메두사는 바라보는 방향으로 90도의 시야각을 가지며, 시야각 범위 안에 있는 전사들을 볼 수 있습니다. 아래 그림은 메두사가 아래 방향을 바라볼 때 시야를 나타냅니다. 

메두사의 시야각 안에 들어와있지만 다른 전사에 가려진 전사의 경우 메두사에게 보이지 않습니다.

특정 전사에 의해 메두사에게 가려지는 범위는 메두사와 해당 전사의 상대적인 위치에 의해 결정됩니다. 상하좌우 대각선 8방향을 나누었을 때, 메두사로부터 8방향 중 한 방향에 전사가 위치해있다면, 그 전사가 동일한 방향으로 바라본 범위에 포함된 모든 칸은 메두사에게 보이지 않습니다. 

메두사가 본 전사들은 모두 돌로 변해 현재 턴에는 움직일 수 없으며, 이번 턴이 종료되었을 때 돌에서 풀려납니다. 만약 두 명 이상의 전사들이 같은 칸에 위치해있다면 해당 칸의 전사들은 모두 돌로 변하게 됩니다.

이때 메두사는 상,하,좌,우 중 전사를 가장 많이 볼 수 있는 방향을 바라봅니다. 같은 수의 전사를 볼 수 있는 방향이 여러 개라면, 상하좌우의 우선순위로 방향을 결정합니다. 아래 그림과 같은 상황에서는 좌측을 바라볼 때 두 명의 전사, 우측을 바라볼 때 한 명의 전사를 볼 수 있으므로 좌측을 바라보게 됩니다.

 [3] 전사들의 이동 

돌로 변하지 않은 전사들은 메두사를 향해 최대 두 칸까지 이동합니다. 전사들은 이동 중 같은 칸을 공유할 수 있습니다.

• 첫 번째 이동
  • 메두사와의 거리를 줄일 수 있는 방향으로 한 칸 이동합니다. 이런 방향이 두 개 이상일 겨ㅑㅇ우 상하좌우의 우선순위로 방향을 선택합니다.
  • 격자의 바깥으로 나갈 수 없으며, 메두사의 시야에 들어오는 곳으로는 이동할 수 없습니다.
• 두 번째 이동
  • 메두사와의 거리를 줄일 수 있는 방향으로 한 칸 더 이동합니다. 이런 방향이 두 개 이상일 경우 좌우상하의 우선순위로 방향을 선택합니다.
  • 격자의 바깥으로 나갈 수 없으며, 메두사의 시야에 들어오는 곳으로는 이동할 수 없습니다.

[4] 전사의 공격

메두사와 같은 칸에 도달한 전사는 메두사를 공격합니다. 그러나 메두사가 너무 강한 나머지 이기지 못하고 사라집니다. 위의 네 단계에서 최단경로를 계산할 때는 맨해튼 거리를 기준으로 합니다. 위의 네 단계가 반복되어 메두사가 공원에 도달할 때까지 매 턴마다 해당 턴에서 모든 전사가 이동한 거리의 합, 메두사로 인해 돌이 된 전사의 수, 메두사를 공격한 전사의 수를 공백을 사이에 두고 차례대로 출력하는 프로그램을 작성하세요. 단, 메두사가 공원에 도착하는 턴에는 0을 출력하고 프로그램을 종료합니다. 

풀이

Code

import sys
from collections import deque
from typing import List, Tuple
input = sys.stdin.readline

# 1. 메두사 클래스 생성
class Medusa:
    # 1-1.
    def __init__(self,
                 Sr:int,
                 Sc:int,
                 Er:int,
                 Ec:int):
        # 1-1-1. 메두사 위치 선언
        self.index = (Sr, Sc)
        # 1-1-2. 공원 위치 선언
        self.park = (Er, Ec)
        # 1-1-3. 메두사 이동 경로 생성
        self.route = self._get_route(Sr, Sc)
        # 1-1-4. 방향 별 시야 딕셔너리 생성
        self.dirs = {
            (-1, 0): [(-1, -1), (-1, 0), (-1, 1)],
            (1, 0): [(1, -1), (1, 0), (1, 1)],
            (0, -1): [(-1, -1), (0, -1), (1, -1)],
            (0, 1): [(-1, 1), (0, 1), (1, 1)]
        }
    # 1-2. 최단 경로 선정 함수 생성
    def _get_route(self,
                   Sr:int,
                   Sc:int) -> List[Tuple]:
        # 1-2-1. 큐 생성 후 메두사 위치 삽입
        queue = deque([(Sr, Sc)])
        # 1-2-2. 역추적 그래프 후 현재 위치 방문 처리
        backtracking_graph = [[False for _ in range(N)] for _ in range(N)]
        backtracking_graph[Sr][Sc] = True
        # 1-2-3.
        while queue:
            # 위치 인덱스 반환
            x, y = queue.popleft()
            for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                # 다음 위치 설정
                nx, ny = x+dir_x, y+dir_y
                # 예외 처리
                if nx<0 or nx>=N or ny<0 or ny>=N or graph[nx][ny] == 1: continue
                # 다음 위치에 방문한 적이 없는 경우
                if not backtracking_graph[nx][ny]:
                    # 역추적 그래프에 현재 위치 삽입
                    backtracking_graph[nx][ny] = (x, y)
                    # 공원에 도달한 경우
                    if (nx, ny) == self.park:
                        # 이동경로 리스트 생성 및 반환
                        route = []
                        Rx, Ry = nx, ny
                        while backtracking_graph[Rx][Ry] != True:
                            route.append((Rx, Ry))
                            Rx, Ry = backtracking_graph[Rx][Ry]
                        return route[::-1]
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
        # 1-2-4. 공원에 도달하지 못했으므로 빈 리스트 반환
        return []

    # 1-3. 이동 함수 생성
    def move(self, warrior_graph) -> None:
        self.warrior_graph = warrior_graph

        # 1-3-1. 메두사 위치 업데이트
        self.index = self.route.pop(0)
        # 1-3-2. 이동한 곳에 전사가 있는 경우 처리
        x, y = self.index
        if self.warrior_graph[x][y]:
            self.warrior_graph[x][y] = 0

    # 1-4. 메두사 시야 추출 함수 생성
    def _view_extract(self, dir:Tuple) -> List[List[bool]]:
        # 1-4-1. 큐 생성 후 메두사 위치 삽입
        x, y = self.index
        queue = deque([(x, y)])
        # 1-4-2. 시야 여부 그래프 생성
        visible_graph = [[False for _ in range(N)] for _ in range(N)]
        # 1-4-3. 시야 내 전사 리스트 생성
        exposed_warriors = []
        # 1-4-4.
        while queue:
            # 위치 인덱스 반환
            x, y = queue.popleft()
            for dir_x, dir_y in self.dirs[dir]:
                # 다음 위치 설정
                nx, ny = x+dir_x, y+dir_y
                # 예외 처리
                if nx<0 or nx>=N or ny<0 or ny>=N: continue
                # 해당 위치를 본 적이 없는 경우
                if not visible_graph[nx][ny]:
                    # 시야 처리
                    visible_graph[nx][ny] = True
                    # 해당 위치에 전사가 있는 경우 시야 내 전사 리스트 업데이트
                    if self.warrior_graph[nx][ny] :
                        exposed_warriors.append((nx, ny))
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
        # 1-4-5.
        for x, y in exposed_warriors:
            # 전사 위치가 메두사 시야에 노출된 경우
            if visible_graph[x][y]:
                # 메두사로부터의 방향 선정
                diff_x = x - self.index[0]
                diff_y = y - self.index[1]
                warrior_dirs = [
                    self.dirs[dir][1],
                    (
                        int(diff_x/abs(diff_x)) if diff_x else 0,
                        int(diff_y/abs(diff_y)) if diff_y else 0
                    )
                ]
                # 큐 생성 후 전사 위치 삽입
                queue = deque([(x, y)])
                while queue:
                    # 위치 인덱스 반환
                    x, y = queue.popleft()
                    for dir_x, dir_y in warrior_dirs:
                        # 다음 위치 설정
                        nx, ny = x+dir_x, y+dir_y
                        # 예외 처리
                        if nx<0 or nx>=N or ny<0 or ny>=N: continue
                        # 해당 위치가 보이는 경우
                        if visible_graph[nx][ny]:
                            # 시야 처리
                            visible_graph[nx][ny] = False
                            # 큐에 다음 위치 삽입
                            queue.append((nx, ny))
        # 1-4-6. 시야 여부 그래프 반환
        return visible_graph

    # 1-5. 노출된 전사 수 체크 함수 생성
    def _check_warriors(self,
                        visible_graph:List[List[bool]]) -> int:
        cnt = 0
        # 1-5-1.
        for x in range(N):
            for y in range(N):
                # 시야가 노출된 경우 전사 수 카운트
                if visible_graph[x][y]:
                    cnt += self.warrior_graph[x][y]
        # 1-5-2. 노출된 전사 수 반환
        return cnt

    # 1-6. 메두사 시선 함수 생성
    def gaze(self) -> None:
        # 1-6-1. 노출된 전사 수 초기화 선언
        self.warrior_cnt = 0
        # 1-6-2.
        for dir in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            # 메두사 시야 추출
            visible_graph = self._view_extract(dir)
            # 노출된 전사 수 체크
            # 노출된 전사 수가 선언된 값보다 많을 경우
            if self.warrior_cnt < (warrior_cnt:=self._check_warriors(visible_graph)):
                # 노출된 전사 수 업데이트
                self.warrior_cnt = warrior_cnt
                # 시야 그래프 선언
                self.visible_graph = visible_graph

# 2. 전사 클래스 생성
class Warrior:
    # 2-1.
    def __init__(self,
                 warriors:List[Tuple]):
        # 2-1-1. 전사 인덱스 리스트 선언
        self.warriors = warriors
        # 2-1-2. 전사 위치 그래프 생성
        self.warrior_graph = self._create_warrior_graph()

    # 2-2. 전사 위치 그래프 생성 함수 생성
    def _create_warrior_graph(self) -> List[List[int]]:
        # 2-2-1. 전사 위치 그래프 초기화
        warrior_graph = [[0 for _ in range(N)] for _ in range(N)]
        # 2-2-2.
        for warrior in self.warriors:
            # 전사 위치 그래프 업데이트
            x, y = warrior
            warrior_graph[x][y] += 1
        # 2-2-3. 전사 위치 그래프 반환
        return warrior_graph

    # 2-3. 우선 순위에 따른 이동 함수 생성
    def _move(self,
              warrior_x:int,
              warrior_y:int,
              priority_dirs:List[Tuple]) -> Tuple[int]:
        # 2-3-1.
        for dir_x, dir_y in priority_dirs:
            # 다음 위치 설정
            nx, ny = warrior_x+dir_x, warrior_y+dir_y
            # 예외 처리
            if nx<0 or nx>=N or ny<0 or ny>=N: continue
            # 다음 위치가 메두사의 시야 내에서 벗어나면서 메두사와 가까워지는 경우
            mx, my = self.medusa_index
            if not self.visible_graph[nx][ny] and abs(mx-warrior_x)+abs(my-warrior_y) > abs(mx-nx)+abs(my-ny):
                # 다음 위치 반환
                return (nx, ny)
        # 2-3-2. 이동이 불가하므로 현재 위치 반환
        return (warrior_x, warrior_y)

    # 2-4. 이동 함수 생성
    def move(self, warrior_graph, medusa_index, visible_graph) -> None:
        self.warrior_graph = warrior_graph
        self.medusa_index, self.visible_graph = medusa_index, visible_graph
        self.sub_warrior_graph = [[0 for _ in range(N)] for _ in range(N)]

        # 2-4-1. 이동 거리 및 공격 횟수 선언
        self.distance, self.attack_cnt = 0, 0
        # 2-4-2.
        for x in range(N):
            for y in range(N):
                # 현재 위치가 메두사의 시야에서 벗어나면서 기사가 있는 경우
                if not self.visible_graph[x][y] and self.warrior_graph[x][y]:
                    px, py = x, y
                    for priority_dirs in [
                        [(-1, 0), (1, 0), (0, -1), (0, 1)],
                        [(0, -1), (0, 1), (-1, 0), (1, 0)]
                    ]:
                        # 우선 순위에 따른 이동
                        nx, ny = self._move(px, py, priority_dirs)
                        # 이동을 하지 않은 경우 break
                        if (px, py) == (nx, ny):
                            break
                        # 이동 처리
                        else:
                            self.distance += self.warrior_graph[x][y]
                        # 메두사에게 도달한 경우
                        if (nx, ny) == self.medusa_index:
                            # 공격 횟수 업데이트
                            self.attack_cnt += self.warrior_graph[x][y]
                            break
                        px, py = nx, ny
                    # 이동이 마무리되었다면 이동 처리
                    if (nx, ny) != self.medusa_index:
                        self.sub_warrior_graph[nx][ny] += self.warrior_graph[x][y]
                # 기사가 움직일 수 없는 경우 전사 위치 그래프 업데이트
                elif self.warrior_graph[x][y]:
                    self.sub_warrior_graph[x][y] += self.warrior_graph[x][y]
        # 2-4-3. 전사 위치 그래프 업데이트
        self.warrior_graph = self.sub_warrior_graph[:][:]

N, M = map(int, input().split())
Sr, Sc, Er, Ec = map(int, input().split())
length = len(sub_index:=list(map(int, input().split())))
warriors = [(sub_index[idx], sub_index[idx+1]) for idx in range(0, length, 2)]
graph = [list(map(int, input().split())) for _ in range(N)]

# 3. 전사 object 생성
warrior = Warrior(warriors)
# 4. 메두사 object 생성
medusa = Medusa(Sr, Sc, Er, Ec)
# 5. 이동 경로가 존재하지 않는 경우 -1 출력
if not medusa.route:
    print(-1)
else:
    # 6.
    while True:
        # 6-1. 메두사 이동
        medusa.move(warrior_graph=warrior.warrior_graph)
        # 6-2. 메두사가 공원에 도착한 경우 0 출력 후 while문 탈출
        if medusa.index == (Er, Ec):
            print(0)
            break
        # 6-3. 메두사 시선
        medusa.gaze()
        # 6-4. 전사 이동 및 공격
        warrior.move(warrior_graph=warrior.warrior_graph,
                     medusa_index=medusa.index,
                     visible_graph=medusa.visible_graph)
        # 6-5. 결과 출력
        print(warrior.distance, medusa.warrior_cnt, warrior.attack_cnt)