[Python/Codetree] 술래 잡기

https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20

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

문제

술래잡기 게임을 진행해보려고 합니다. 술래잡기 게임은 n * n 크기의 격자에서 진행되며 술래는 처음 정중앙에 서있습니다.

술래잡기 게임에는 m명의 도망자가 있습니다. 도망자는 처음 지정된 곳에 서있습니다. 도망자는 중앙에서 시작하지는 않습니다. 도망자의 종류는 좌우로만 움직이는 유형과 상하로만 움직이는 유형 이렇게 2가지가 있습니다. 이때 좌우로 움직이는 사람은 항상 오른쪽을 보고 시작하며, 상하로 움직이는 사람은 항상 아래쪽을 보고 시작합니다.

예로 3명의 도망자(m = 3)가 주어진 경우를 가정해보겠습니다.

또, 이 술래잡기 게임에는 h개의 나무가 있습니다.

예로 하나의 나무(h = 1)가 있는 경우를 가정해보겠습니다. 이처럼 나무가 도망자와 초기에 겹쳐져 주어지는 것 역시 가능합니다.

 

술래잡기 게임에서는 m명의 도망자가 먼저 동시에 움직이고, 그 다음 술래가 움직이고, 도망자가 움직이고, 술래가 움직이고, ... 이렇게 도망자가 1턴 그리고 이어서 술래가 1턴 진행하는 것을 총 k번 반복하게 됩니다.

이때 도망자가 움직일 때 현재 술래와의 거리가 3 이하인 도망자만 움직입니다. 도망자의 위치가 (x1, y1), 술래의 위치가 (x2, y2)라 했을 때 두 사람간의 거리는 |x1 - x2| + |y1 - y2|로 정의됩니다.

술래와의 거리가 3 이하인 도망자들은 1턴 동안 다음 규칙에 따라 움직이게 됩니다.

• 현재 바라보고 있는 방향으로 1칸 움직인다 했을 때 격자를 벗어나지 않는 경우
  • 움직이려는 칸에 술래가 있는 경우라면 움직이지 않습니다.
  • 움직이려는 칸에 술래가 있지 않다면 해당 칸으로 이동합니다. 해당 칸에 나무가 있어도 괜찮습니다.
• 현재 바라보고 있는 방향으로 1칸 움직인다 했을 때 격자를 벗어나는 경우
• 먼저 방향을 반대로 틀어줍니다. 이후 바라보고 있는 방향으로 1칸 움직인다 했을 때 해당 위치에 술래가 없다면 1칸 앞으로 이동합니다.

위의 규칙에 따라 <Figure 3>에서 도망자가 1턴 동안 움직인 이후의 모습은 다음과 같습니다.

이후 술래가 1턴 움직이는 경우를 살펴보겠습니다.

술래는 처음 위 방향으로 시작하여 달팽이 모양으로 움직입니다.

만약 끝에 도달하게 되면 다시 거꾸로 중심으로 이동하고, 다시 중심에 오게 되면 처음처럼 위 방향으로 시작하여 시계뱡향으로 도는 것을 k턴에 걸쳐 반복하게 됩니다.

술래는 1번의 턴 동안 정확히 한 칸 해당하는 방향으로 이동하게 됩니다. 이동 후의 위치가 만약 이동방향이 틀어지는 지점이라면, 방향을 바로 틀어줍니다. 만약 이동을 통해 양끝에 해당하는 위치인 (1행, 1열) 혹은 정중앙에 도달하게 된다면 이 경우 역시 방향을 바로 틀어줘야 함에 유의합니다. <Figure 4>에서 술래가 한 칸 이동하게 되면, 술래는 바로 방향을 틀게 됩니다.

이동 직후 술래는 턴을 넘기기 전에 시야 내에 있는 도망자를 잡게 됩니다. 술래의 시야는 현재 바라보고 있는 방향을 기준으로 현재 칸을 포함하여 총 3칸입니다. 격자 크기에 상관없이 술래의 시야는 항상 3칸임에 유의합니다.

하지만 만약 나무가 놓여 있는 칸이라면, 해당 칸에 있는 도망자는 나무에 가려져 보이지 않게 됩니다. 따라서 <Figure 8>의 경우에서는 (2행, 5열)에 있는 도망자만 잡히게 됩니다. 잡힌 도망자는 사라지게 되고, 술래는 현재 턴을 t번째 턴이라고 했을 때 t x 현재 턴에서 잡힌 도망자의 수만큼의 점수를 얻게 됩니다. 따라서 <Figure 8>의 상황에서 술래는 1 x 1인 1점을 얻게 되고 (2행, 5열)에 있던 도망자는 사라지게 됩니다.

그 다음에는 다시 도망자의 턴이 진행되고, 이어서 술래의 턴이 진행되는 것을 총 k번에 걸쳐 반복하게 됩니다.

만약 k = 2였다면, 이제 2번째 턴이 진행되어야 합니다.

2번째 턴에서 먼저 도망자가 움직이게 됩니다.

이후 술래는 한 칸 앞으로 움직이게 됩니다. 이때 역시 이동방향이 틀어지는 지점이므로, 이동후 바로 방향을 틀게 됩니다. 이 경우 남은 두 도망자가 모두 잡히게 되어 2(번째 턴) x 2(명의 도망자)에 해당하는 4점을 추가적으로 얻게 됩니다.

k번에 걸쳐 술래잡기를 진행하는 동안 술래가 총 얻게된 점수를 출력하는 프로그램을 작성해보세요.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 술래와 도망자 간 거리 계산 함수 정의
def distance(x, y) :
    # 1-1. 거리 반환
    return abs(tagger_x - x) + abs(tagger_y - y)
# 2. 도망자 이동 함수 정의
def move_runaway() :
    # 2-1. 도망자 이동 함수 정의
    for runaway in runaways :
        x, y = information[runaway]["location"]
        # 2-1-1. 술래와의 거리가 3 초과일 경우 continue
        if distance(x, y) > 3 :
            continue
        # 2-1-2. 다음 위치 설정
        dir_x, dir_y = information[runaway]["dir"]
        nx, ny = x + dir_x, y + dir_y
        # 2-1-3. 맵을 벗어난 경우
        if nx < 1 or nx > n or ny < 1 or ny > n :
            # 방향 전환 후 다음 위치 재설정
            dir_x *= -1
            dir_y *= -1
            information[runaway]["dir"] = (dir_x, dir_y)
            nx, ny = x + dir_x, y + dir_y
        # 2-1-4. 다음 위치에 술래가 없는 경우
        if (nx, ny) != (tagger_x, tagger_y) :
            # 이동
            information[runaway]["location"] = (nx, ny)
            graph[(x, y)].remove(runaway)
            graph[(nx, ny)].append(runaway)
# 3. 시계 방향 회전 함수 정의
def mode_clockwise() :
    global mode, tagger_x, tagger_y, tagger_dir, cnt, rotate_cnt, how
    # 3-1. 마지막 라인에 있는 경우
    if tagger_y == 1 :
        # 3-1-1. 이동
        tagger_x -= 1
        # 3-1-2. (1, 1)에 도착한 경우
        if (tagger_x, tagger_y) == (1, 1) :
            # 모드 변경
            mode = "counterclockwise"
            # 방향 변경
            tagger_dir = 2
    # 3-2. 이외의 경우
    else :
        tagger_x += dirs[tagger_dir][0]
        tagger_y += dirs[tagger_dir][1]
        cnt += 1
        # 이동 방향이 틀어지는 지점일 경우 방향 변동
        if cnt == how :
            tagger_dir = (tagger_dir + 1) % 4
            # 이동 칸 수 증가 시
            rotate_cnt -= 1
            if rotate_cnt == 0 :
                rotate_cnt = 2
                if tagger_y != 1 : how += 1
            cnt = 0
# 4. 반시계 방향 함수 정의
def mode_counterclockwise() :
    global mode, tagger_x, tagger_y, tagger_dir, cnt, rotate_cnt, how
    # 4-1. 첫 라인에 있는 경우
    if tagger_x != n and tagger_y == 1 :
        # 4-1-1. 이동
        tagger_x += 1
        # 4-1-2. 첫 라인의 끝에 도달한 경우
        if tagger_x == n :
            tagger_dir -= 1
    # 4-2. 이외의 경우
    else :
        tagger_x += dirs[tagger_dir][0]
        tagger_y += dirs[tagger_dir][1]
        # 4-2-1. 중심 지점에 도착한 경우
        if (tagger_x, tagger_y) == (n // 2 + 1, n // 2 + 1) :
            # 모드 변경
            mode = "clockwise"
            # 방향 변경
            tagger_dir = 0
            rotate_cnt = 2
        # 4-2-2. 이외의 경우
        else :
            cnt += 1
            # 이동 방향이 틀어지는 지점일 경우 방향 변동
            if cnt == how :
                tagger_dir = (tagger_dir - 1) % 4
                # 이동 칸 수 증가 시
                rotate_cnt -= 1
                if rotate_cnt == 0 :
                    rotate_cnt = 2
                    if tagger_y != 1 : how -= 1
                cnt = 0
# 5. 시야 내 도망자 검거 함수 정의
def checkmate() :
    global score
    # 5-1.
    for i in range(3) :
        # 5-1-1. 시야 인덱스 설정
        cx, cy = tagger_x + dirs[tagger_dir][0] * i, tagger_y + dirs[tagger_dir][1] * i
        # 5-1-2. 맵을 벗어나는 경우
        if cx < 1 or cx > n or cy < 1 or cy > n : break
        # 5-1-3. 해당 위치에 나무가 있을 경우
        try :
            if trees[(cx, cy)] : continue
        # 5-1-4. 해당 위치에 나무가 없을 경우
        except :
            # 해당 위치에 사람이 있을 경우
            for runaway in graph[(cx, cy)] :
                # 스코어 업데이트
                score += round
                # 남아있는 도망자 리스트 업데이트
                runaways.remove(runaway)
            else :
                graph[(cx, cy)] = []

# 6. 술래 이동 함수 정의
def move_tagger() :
    # 6-1. 술래 이동
    mode_clockwise() if mode == "clockwise" else mode_counterclockwise()
    # 6-2. 도망자 검거
    checkmate()

if __name__ == "__main__" :
    n, m, h, k = map(int, input().split())
    # 7. 도망자 정보 딕셔너리 생성
    # 8. 그래프 내 도망자 정보 생성
    information = {}
    graph = {}
    for i in range(1, n + 1) :
        for j in range(1, n + 1) :
            graph[(i, j)] = []
    for idx in range(m) :
        x, y, dir = map(int, input().split())
        information[idx] = {"location" : (x, y), "dir" : (0, 1)} if dir == 1 else {"location" : (x, y), "dir" : (1, 0)}
        graph[(x, y)].append(idx)
    # 9. 현재 남아있는 도망자 리스트 생성
    runaways = list(range(m))
    # 10. 나무 위치 정의
    trees = {}
    for _ in range(h) :
        trees[tuple(map(int, input().split()))] = True
    # 11. 술래 위치 정의
    tagger_x, tagger_y = n // 2 + 1, n // 2 + 1
    # 12. 술래 방향 변수 생성
    tagger_dir = 0
    # 13. 술래 회전 방향 변수 생성
    mode = "clockwise"
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cnt, rotate_cnt, how = 0, 2, 1
    score = 0
    # 14.
    for round in range(1, k+1) :
        # 14-1. 도망자 이동
        move_runaway()
        # 14-2. 술래 이동
        move_tagger()
        # 14-3. 도망자가 없을 경우 탈출
        if not runaways : break
    # 15. 결과 출력
    print(score)