[python] 코드 트리 - 술래잡기

문제

https://www.codetree.ai/frequent-problems/hide-and-seek/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이

문제에 적힌대로 하나씩 구현해나가면 어렵지 않게 풀수 있는 문제다. 

문제에서 술래가 달팽이 회전(토네이도 회전?) 으로 움직이게 되는데, 해당 부분만 신경써서 구현하면 될꺼같다.

술래가 움직이는 순서

문제를 읽고 구현해야될 부분을 다음과 같이 정리했다. 

 

1. 도망자의 초기 위치 관련

•  도망자는 처음 지정된 곳에 서있음.
•  중앙에서 시작하지 않음 (술래랑 겹치지 않음)
•  도망자의 종류는 좌우로만 움직이는 유형과 상하로만 움직이는 유형 이렇게 2가지가 존재
•  이때 좌우로 움직이는 사람은 항상 오른쪽을 보고 시작
•  상하로 움직이는 사람은 항상 아래쪽 보고 시작

 

2. 도망자의 움직임 관련

• 도망자의 위치와 술래의 위치의 거리가 3 이하인 경우에만 움직인다.
  • 도망자의 위치가 (x1, y1), 술래의 위치가 (x2, y2)라 했을 때 두 사람간의 거리는 |x1 - x2| + |y1 - y2|로 정의
• 현재 바라보고 있는 방향으로 1칸 움직임
• 움직이려는 칸에 술래가 있으면 움직이지 않음
• 움직였을때 격자를 벗어 난다면
  • 우선 뱡항을 반대방향으로 바꾸고(뒤로 돌고) ,
  • 해당 방향으로 1칸 전진 했을때 술래가 없으면 움직인다.

 

3. 나무의 위치

• 나무의 초기 위치는 도망자의 초기 위치와 겹칠 수 있다.

 

4. 술래의 움직임 관련

• 정중앙에서 달팽이 모양으로 움직임
• 끝 (0,0) 에 도달하게 되면 다시 거꾸로 중심으로 이동
• 1턴에 1칸씩 술래가 바라보는 방향으로 이동
• 이동 후 위치가 이동방향이 틀어지는 시점이라면 방향을 바로 틀어줌. 
  • 해당 조건 때문에, 술래의 움직임은 정방향일때와 역방향 일때를 모두 구해줘야함.
• 움직인 이후 시야에 있는 도망자를 잡으며, 시야는 현재 바라보고 있는 방향을 기준으로 현재 칸 포함 3칸
• 나무가 있는 칸에 있는 도망자는 잡을 수 없다.
• 만약 술래가 1칸 이동했는데,
  • 도망자가 있다 -> 잡음
  • 도망자도 있지만 나무도 있다. -> 못잡음

 

5. 게임 진행

• 도망자가 먼저 움직이고,  그 다음에 술래가 움직인다.

 

 

코드

import sys

# n: 격자의 크기, m: 도망자의 수, h: 나무의 수, k: 턴 수
n, m, h, k = map(int, sys.stdin.readline().split())

# 도망자(runner) 정보와 나무(tree) 정보를 저장할 리스트
runner = []
tree = []

# m개의 도망자 정보를 입력받음 (y 좌표, x 좌표, 이동 방향)
for _ in range(m):
    temp_ = list(map(int, sys.stdin.readline().split()))
    runner.append(temp_)

# h개의 나무 정보를 입력받음 (y 좌표, x 좌표)
for _ in range(h):
    temp_ = list(map(int, sys.stdin.readline().split()))
    tree.append(temp_)

# answer: 잡힌 도망자의 수 (초기값 0)
answer = 0

# 이동 방향 (상, 우, 하, 좌)
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]


# 도망자들의 움직임을 처리하는 함수
def runner_move(turn: int) -> None:
    """
    주어진 턴에 도망자들이 움직임을 처리함.

    Args:
        turn (int): 현재 턴 번호
    """
    global n, runner
    catcher_x, catcher_y, _ = catcher_path[turn]
    new_runner = []

    # 각 도망자마다 움직임 처리
    for idx, run in enumerate(runner):
        run_x, run_y, run_d = run
        # 술래와 거리가 3 이상이면 움직이지 않음
        dist = abs(catcher_x - run_x) + abs(catcher_y - run_y)
        if dist > 3:
            new_runner.append(run)
            continue

        # 도망자가 (-1, -1) 즉 이미 잡혔으면 넘어감
        if (run_x, run_y) == (-1, -1):
            continue

        # 도망자의 다음 위치
        ny = run_y + dy[run_d]
        nx = run_x + dx[run_d]

        # 움직이려는 위치에 술래가 있으면 이동하지 않음
        if (nx, ny) == (catcher_x, catcher_y):
            new_runner.append(run)
            continue

        # 격자 내에 있으면 이동
        if 0 <= nx < n and 0 <= ny < n:
            new_runner.append([nx, ny, run_d])
        # 격자 밖으로 나가면 방향을 바꿈
        else:
            if ny < 0:
                run_d = 2  # 하향
            elif nx < 0:
                run_d = 1  # 우향
            elif ny == n:
                run_d = 0  # 상향
            elif nx == n:
                run_d = 3  # 좌향

            ny = run_y + dy[run_d]
            nx = run_x + dx[run_d]

            # 움직이려는 위치에 술래가 있으면 방향만 바꾸고 제자리에
            if (nx, ny) == (catcher_x, catcher_y):
                new_runner.append([run_x, run_y, run_d])
            else:
                new_runner.append([nx, ny, run_d])

    # 도망자 리스트 업데이트
    runner = new_runner


# 술래가 도망자를 잡는 함수
def catcher_catch(turn: int, score: int) -> None:
    """
    술래가 주어진 턴에 도망자를 잡는 함수.

    Args:
        turn (int): 현재 턴 번호
        score (int): 현재 턴의 점수
    """
    global answer
    if turn == 47:
        turn = -1

    catcher_x, catcher_y, catcher_d = catcher_path[turn + 1]

    # 3칸까지 잡기 시도
    for i in range(3):
        nx = catcher_x + (dx[catcher_d] * i)
        ny = catcher_y + (dy[catcher_d] * i)

        # 격자 내에 있을 경우
        if 0 <= nx < n and 0 <= ny < n:
            for idx, run in enumerate(runner):
                # 나무가 있으면 잡을 수 없음
                if (nx, ny) in tree:
                    continue
                # 도망자를 잡았을 경우
                elif (nx, ny) == (run[0], run[1]):
                    answer = answer + score + 1
                    runner[idx] = [-1, -1, -1]  # 도망자를 잡았음을 표시


# 술래의 이동 경로를 계산하는 함수
def get_catcher_path() -> list[list[int]]:
    """
    술래의 이동 경로를 계산하여 반환하는 함수.

    Returns:
        list[list[int]]: 술래가 이동할 경로 (좌표와 방향)
    """
    path = []
    x, y = n // 2, n // 2  # 시작 위치 (격자 중앙)
    distance = 1  # 각 방향으로 이동할 거리
    direction = 0  # 현재 방향 (상, 우, 하, 좌)

    while len(path) < n * n:
        for _ in range(2):
            for __ in range(distance):
                path.append([x, y, direction])
                if len(path) == n * n:
                    return path
                x += dx[direction]
                y += dy[direction]
            direction = (direction + 1) % 4  # 방향 전환
        distance += 1  # 이동 거리 증가

    return path


# 술래의 역방향 이동 경로를 계산하는 함수
def get_catcher_reverse_path() -> list[list[int]]:
    """
    술래의 역방향 이동 경로를 계산하여 반환하는 함수.

    Returns:
        list[list[int]]: 술래의 역방향 이동 경로 (좌표와 방향)
    """
    path = []

    # 좌상단부터 우측으로 진행하는 경로
    for i in range(n - 1):
        path.append([0, i, 2])

    x, y = 0, n - 1  # 시작 위치
    distance = n - 1
    direction = 1  # 초기 방향 (우향)

    while len(path) < (n * n) - 1:
        for _ in range(2):
            for __ in range(distance):
                path.append([x, y, direction])
                if len(path) == (n * n) - 1:
                    return path
                x += dx[direction]
                y += dy[direction]
            direction = (direction - 1) % 4  # 방향 전환
        distance -= 1  # 이동 거리 감소

    return path


# 술래의 경로 설정
catcher_path = get_catcher_path()
catcher_reverse_path = get_catcher_reverse_path()
catcher_path = catcher_path[:-1] + catcher_reverse_path

# 도망자와 나무 좌표 조정 (1-indexed에서 0-indexed로 변환)
for i in range(len(runner)):
    runner[i] = [runner[i][1] - 1, runner[i][0] - 1, runner[i][2]]

for i in range(len(tree)):
    tree[i] = (tree[i][1] - 1, tree[i][0] - 1)

# 시뮬레이션 시작
for idx in range(k):
    runner_move(idx % 48)  # 도망자 이동
    catcher_catch(idx % 48, idx)  # 술래 잡기

# 최종 답안 출력
print(answer)