코드트리 | 술래잡기 | 나선형 알고리즘 (밖->안, 안->밖)

문제

링크

풀이

크게 도망자 이동 그리고 술래 이동이 세트가 되어 하나의 턴을 이루고 있다.
도망자 이동 함수는 매우 쉽게 구현 가능하고 술래 이동이 굉장히 까다롭다

하나의 턴 안에 나선형 알고리즘을 온전히 사용하는 것이 아니라 하나의 턴마다 한 칸식 나선형 알고리즘에 따라 이동해야하며, 심지어 (0,0)에 도달했다면 다시 거꾸로 왔던 경로대로 한칸씩 돌아가야 한다 ; 추가로 이동방향이 틀어지는 시점이라면 방향 역시 바로 틀어주어야 하는 쓰리콤보 고약한 문제..

그러나 미리 정방향 나선형 경로와 역방향 나선형 경로를 지정해주고 그에 맞춰서 가면 생각보다 빠르게 구현할 수 있을지도 모른다. 일단 나는 아니었으니 패스..

아무튼 여기서 포인트는 정방향 경로와 역방향 경로를 빠르게 탐색하는 게 관건이다.

def initialize_seeker_path():
    initialize_seeker_next_path()
    initialize_seeker_rev_path()

def initialize_seeker_next_path():
    # 상우하좌 순서대로 넣어줍니다.
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    y = n // 2
    x = n // 2
    dist = 1
    move_count = 0  # 2가 되면 dist+1하고 move_count는 다시 초기화
    d_idx = 0
    while 1:
        for _ in range(dist):
            dy, dx = d[d_idx]
            y = y + dy
            x = x + dx
            seeker_next_dir[y][x] = d_idx
            if (y, x) == (-1, 0):
                return
        d_idx = (d_idx + 1) % 4
        seeker_next_dir[y][x] = d_idx
        move_count += 1
        if move_count == 2:
            dist += 1
            move_count = 0
            
 def initialize_seeker_rev_path():
    # d=[(1,0),(0,1),(-1,0),(0,-1)]
    y,x=0,0
    d_idx=0
    for i in range(n*n):
        seeker_rev_dir[y][x]=flip_dir(d_idx)
        # 방향 자체는 하나로 일관되어야 하기 때문에 정방향에서 쓰인 방향으로 인덱스를 바꿔서 저장한다
        if d_idx==0:
            y+=1
            if y==n-1 or seeker_rev_dir[y+1][x]!=-1:
                d_idx=1
        elif d_idx == 1:
            x += 1
            if x == n - 1 or seeker_rev_dir[y][x+1] != -1:
                d_idx = 2
        elif d_idx == 2:
            y -= 1
            if y == 0 or seeker_rev_dir[y-1][x] != -1:
                d_idx = 3
        elif d_idx == 3:
            x -= 1
            if x == n - 1 or seeker_rev_dir[y][x-1] != -1:
                d_idx = 0

그럼 이런식으로 정/역방향 별 각 칸의 방향인덱스를 담은 배열을 두 개 만들어낼 수 있다.

여기서 현재 술래가 정방향인지 역방향인지, 끝에 도달했는지(정방향의 경우 (0,0)이고 역방향의 경우 (n//2,n//2))도 추가적으로 고려해주면 된다.

전체 코드

# 변수 선언 및 입력:
n, m, h, k = tuple(map(int, input().split()))

# 각 칸에 있는 도망자 정보를 관리합니다.
# 도망자의 방향만 저장하면 충분합니다.
hiders = [
    [[] for _ in range(n)]
    for _ in range(n)
]
next_hiders = [
    [[] for _ in range(n)]
    for _ in range(n)
]
tree = [
    [False] * n
    for _ in range(n)
]

def flip_dir(d_idx):
    if d_idx==0:
        return 2
    elif d_idx==2:
        return 0
    return d_idx
# 정방향 기준으로
# 현재 위치에서 술래가 움직여야 할 방향을 관리합니다.
seeker_next_dir = [
    [0] * n
    for _ in range(n)
]
# 역방향 기준으로
# 현재 위치에서 술래가 움직여야 할 방향을 관리합니다.
seeker_rev_dir = [
    [-1] * n
    for _ in range(n)
]


# 술래의 현재 위치를 나타냅니다.
seeker_pos = (n // 2, n // 2)
# 술래가 움직이는 방향이 정방향이면 True / 아니라면 False입니다.
forward_facing = True

ans = 0

# 술래 정보를 입력받습니다.
for _ in range(m):
    x, y, d = tuple(map(int, input().split()))
    hiders[x - 1][y - 1].append(d)

# 나무 정보를 입력받습니다.
for _ in range(h):
    x, y = tuple(map(int, input().split()))
    tree[x - 1][y - 1] = True


def initialize_seeker_next_path():
    # 상우하좌 순서대로 넣어줍니다.
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    y = n // 2
    x = n // 2
    dist = 1
    move_count = 0  # 2가 되면 dist+1하고 move_count는 다시 초기화
    d_idx = 0
    while 1:
        for _ in range(dist):
            dy, dx = d[d_idx]
            y = y + dy
            x = x + dx
            seeker_next_dir[y][x] = d_idx
            if (y, x) == (-1, 0):
                return
        d_idx = (d_idx + 1) % 4
        seeker_next_dir[y][x] = d_idx
        move_count += 1
        if move_count == 2:
            dist += 1
            move_count = 0

def initialize_seeker_rev_path():
    # d=[(1,0),(0,1),(-1,0),(0,-1)]
    y,x=0,0
    d_idx=0
    for i in range(n*n):
        seeker_rev_dir[y][x]=flip_dir(d_idx)
        if d_idx==0:
            y+=1
            if y==n-1 or seeker_rev_dir[y+1][x]!=-1:
                d_idx=1
        elif d_idx == 1:
            x += 1
            if x == n - 1 or seeker_rev_dir[y][x+1] != -1:
                d_idx = 2
        elif d_idx == 2:
            y -= 1
            if y == 0 or seeker_rev_dir[y-1][x] != -1:
                d_idx = 3
        elif d_idx == 3:
            x -= 1
            if x == n - 1 or seeker_rev_dir[y][x-1] != -1:
                d_idx = 0


# 정중앙으로부터 끝까지 움직이는 경로를 계산해줍니다.
def initialize_seeker_path():
    initialize_seeker_next_path()
    initialize_seeker_rev_path()




# 격자 내에 있는지를 판단합니다.
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n


def hider_move(x, y, move_dir):
    dxs, dys = [0, 0, 1, -1], [-1, 1, 0, 0]
    # 좌우하상 순서대로 넣어줍니다.

    nx, ny = x + dxs[move_dir], y + dys[move_dir]
    # Step 1.
    # 만약 격자를 벗어난다면
    # 우선 방향을 틀어줍니다.
    if not in_range(nx, ny):
        # 0 <. 1 , 2 <. 3이 되어야 합니다.
        move_dir = 1 - move_dir if move_dir < 2 else 5 - move_dir
        nx, ny = x + dxs[move_dir], y + dys[move_dir]

    # Step 2.
    # 그 다음 위치에 술래가 없다면 움직여줍니다.
    if (nx, ny) != seeker_pos:
        next_hiders[nx][ny].append(move_dir)
    # 술래가 있다면 더 움직이지 않습니다.
    else:
        next_hiders[x][y].append(move_dir)


def dist_from_seeker(x, y):
    # 현재 술래의 위치를 불러옵니다.
    seeker_x, seeker_y = seeker_pos
    return abs(seeker_x - x) + abs(seeker_y - y)


def hider_move_all():
    # Step 1. next hider를 초기화해줍니다.
    for i in range(n):
        for j in range(n):
            next_hiders[i][j] = []

    # Step 2. hider를 전부 움직여줍니다.
    for i in range(n):
        for j in range(n):
            # 술래와의 거리가 3 이내인 도망자들에 대해서만
            # 움직여줍니다.
            if len(hiders[i][j])>0:
                if dist_from_seeker(i, j) <= 3:
                    for move_dir in hiders[i][j]:
                        hider_move(i, j, move_dir)
                # 그렇지 않다면 현재 위치 그대로 넣어줍니다.
                else:
                    for move_dir in hiders[i][j]:
                        next_hiders[i][j].append(move_dir)

    # Step 3. next hider값을 옮겨줍니다.
    for i in range(n):
        for j in range(n):
            hiders[i][j] = next_hiders[i][j]


# 현재 술래가 바라보는 방향을 가져옵니다.
def get_seeker_dir():
    # 현재 술래의 위치를 불러옵니다.
    x, y = seeker_pos

    # 어느 방향으로 움직여야 하는지에 대한 정보를 가져옵니다.
    move_dir = 0
    if forward_facing:
        move_dir = seeker_next_dir[x][y]
    else:
        move_dir = seeker_rev_dir[x][y]

    return move_dir


def check_facing():
    global forward_facing

    # Case 1. 정방향으로 끝에 다다른 경우라면, 방향을 바꿔줍니다.
    if seeker_pos == (0, 0) and forward_facing:
        forward_facing = False
    # Case 2. 역방향으로 끝에 다다른 경우여도, 방향을 바꿔줍니다.
    if seeker_pos == (n // 2, n // 2) and not forward_facing:
        forward_facing = True


def seeker_move():
    global seeker_pos

    x, y = seeker_pos

    # 상우하좌 순서대로 넣어줍니다.
    dxs, dys = [-1, 0, 1, 0], [0, 1, 0, -1]

    move_dir = get_seeker_dir()

    # 술래를 한 칸 움직여줍니다.
    seeker_pos = (x + dxs[move_dir], y + dys[move_dir])

    # 끝에 도달했다면 방향을 바꿔줘야 합니다.
    check_facing()


def get_score(t):
    global ans

    # 상우하좌 순서대로 넣어줍니다.
    dxs, dys = [-1, 0, 1, 0], [0, 1, 0, -1]

    # 현재 술래의 위치를 불러옵니다.
    x, y = seeker_pos

    # 술래의 방향을 불러옵니다.
    move_dir = get_seeker_dir()

    # 3칸을 바라봅니다.
    for dist in range(3):
        nx, ny = x + dist * dxs[move_dir], y + dist * dys[move_dir]

        # 격자를 벗어나지 않으며 나무가 없는 위치라면
        # 도망자들을 전부 잡게 됩니다.
        if in_range(nx, ny) and not tree[nx][ny]:
            # 해당 위치의 도망자 수 만큼 점수를 얻게 됩니다.
            ans += t * len(hiders[nx][ny])

            # 도망자들이 사라지게 됩니다.
            hiders[nx][ny] = [] # 빈 리스트로 초기화


def simulate(t):
    # 도망자가 움직입니다.
    hider_move_all()

    # 술래가 움직입니다.
    seeker_move()

    # 점수를 얻습니다.
    get_score(t)


# 정중앙으로부터 끝까지 움직이는 경로를 계산해줍니다.

# 술래잡기 시작 전 구현상의 편의를 위해 술래 경로 정보를 미리 계산
initialize_seeker_path()
print('정방향')
for i in range(n):
    print(seeker_next_dir[i])
print('--')
print('역방향')
for i in range(n):
    print(seeker_rev_dir[i])


# k번에 걸쳐 술래잡기를 진행합니다.
for t in range(1, k + 1):
    simulate(t)

print(ans)

화이팅!