[Python][구현] 술래 잡기 - 코드트리

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

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

 

[알고리즘]

• 실수 없이 완벽히 코드를 짜야 풀 수 있는 문제(뭐.. 모든 문제가 그렇다만). 까다로운 문제이다. 
• 술래가 시계방향 회전하는 기능을, 새로운 방법으로 접근해보았다. dist와 direction에 대한 queue를 사용하였다. 
  
  • reverse에 해당하는 queue또한 저장한다.
  • remain_dist로 현재의 direction으로 가야할 남은 거리 값을 저장한다.
  • remain_dist가 0일 경우, dist queue, dirs queue를 pop하여 remain_dist와 현재의 dir를 update한다.
  • 그러나, 0이지만, 술래의 위치가 (0, 0) 일경우, reverse queue로 update하고, (N//2, N//2)일 경우, 정방향의 queue로 update한다. 

[느낀점/깨달은점]

• move_escapers 함수에서, new_board의 값이 제대로 update가 안되는 문제가 있었음.
  
  • 움직이지 않는 도망자의 경우, new_board에 그대로 저장해야한다. 그러나, 아래 코드처럼, = 연산을 사용할 경우, 그 전에 해당 위치로 도망온 도망자들의 정보가 사라진다. extend 로 잘 쓸 것. 사소하지만 큰 실수..

                new_escapers[i][j].extend(escapers[i][j])
                ## new_escapers[i][j] = escapers[i][j] -> 틀림

• 술래가 움직이는 함수에서, (0, 0)이나, (N//2, N//2)일 때에도, queue를 update하고, 현재의 dir과 remain_dist를 update해야하는데, 이를 빼먹었다. detail을 신경 쓰자 !!!

 

[코드]

import sys
from collections import deque
import copy

def print_2d(a):
    for i in a :
        for j in i :
            print(j, end=' ')
        print()
    print('===')
def have_to_escape(i, j, r, c):
    if abs(i-r) + abs(j-c)  <= 3 :
        return True
    else :
        return False
def move_escapers(escapers):
    new_escapers = [[deque() for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if have_to_escape(i, j, follower[0], follower[1]):
                while escapers[i][j] :
                    d = escapers[i][j].popleft()
                    ii = i + dy[d]
                    jj = j + dx[d]

                    if ii < 0 or jj < 0 or ii >=N or jj >=N :
                        d = (d+2) % 4
                        ii = i + dy[d]
                        jj = j + dx[d]
                        if not (follower[0] == ii and follower[1] == jj) :
                            new_escapers[ii][jj].append(d)
                        else :
                            new_escapers[i][j].append(d)

                    else :
                        if not (follower[0] == ii and follower[1] == jj) :
                            new_escapers[ii][jj].append(d)
                        else :
                            new_escapers[i][j].append(d)
            else :
                new_escapers[i][j].extend(escapers[i][j])
    return new_escapers

def move_follower(dists, dirs, remain_dist):
    i, j, d = follower

    ii = i + dy[d]
    jj = j + dx[d]

    follower[0], follower[1] = ii, jj

    remain_dist -= 1

    if remain_dist == 0 :
        if len(dists) != 0 :
            remain_dist = dists.popleft()
            follower[2] = dirs.popleft()
        else :
            if ii == 0 and jj == 0 :
                dists = copy.deepcopy(standard_dists_reverse)
                dirs = copy.deepcopy(standard_dirs_reverse)

                remain_dist = dists.popleft()
                follower[2] = dirs.popleft()
            elif ii == N//2 and jj == N//2 :
                dists = copy.deepcopy(standard_dists)
                dirs = copy.deepcopy(standard_dirs)

                remain_dist = dists.popleft()
                follower[2] = dirs.popleft()

    return follower, remain_dist, dists, dirs


def catch_escapers(k, escapers):
    global answer
    i, j, d = follower
    for dist in range(3):
        ii = i + dy[d] * dist
        jj = j + dx[d] * dist

        if ii < 0 or jj < 0 or ii >=N or jj >=N :
            continue
        if trees[ii][jj] :
            continue

        answer += k * len(escapers[ii][jj])
        escapers[ii][jj] = deque()

    return escapers


dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]


N, M, H, K = map(int, input().split())
escapers = [[deque() for _ in range(N)]for _ in range(N)]
trees = [[0 for _ in range(N)]for _ in range(N)]
follower = [N//2, N//2, 0]
answer = 0
for _ in range(M):
    x, y, d = map(int, input().split())
    escapers[x-1][y-1].append(d)

for _ in range(H):
    x, y = map(int, input().split())
    trees[x-1][y-1] = 1

dists = deque()
dirs = deque()

for i in range(1, N):
    dists.append(i)
    dists.append(i)
dists.append(i)

for i in range(2*N-1):
    dirs.append(i % 4)

standard_dists = copy.deepcopy(dists)
standard_dirs = copy.deepcopy(dirs)
standard_dists_reverse = deque(reversed(standard_dists))
standard_dirs_reverse = deque((d+2) % 4 for d in list(reversed(standard_dirs)))
remain_dist = dists.popleft()
dirs.popleft()

for k in range(1,K+1):
    escapers = move_escapers(escapers)
    follower, remain_dist, dists, dirs = move_follower(dists, dirs, remain_dist)
    escapers = catch_escapers(k,escapers)

print(answer)