[코드트리] 파이썬 - 술래 잡기

코드트리 - 술래 잡기

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

# 소요 시간 - 70분

# 접근 방법

• 구현하기 어려웠던 부분은 술래가 움직이는 달팽이 모양의 방향이었다.
• 정방향과 역방향으로 움직일 때 다음 위치를 미리 나타내줄까 고민하였지만 따로 catcher리스트를 관리하는게 편해보여 정의해주었다.
  • 현재 i, 현재 j, 달팽이 인덱스, 방향, 진행한 칸 수
  • 우선 달팽이 모양으로 움직이는 것을 잘 살펴보면, 현재 위치를 제외하고 1 1 2 2 3 3 4 4 칸씩을 가면서 방향을 회전한다.
  • 조금 더 디테일 하게는 방향을 전환했을 때, 위나 아래를 보고 있다면 가야 되는 길이가 +1씩 된다.
• 또한, 나무와 모든 도망자들이 겹칠 수 있기에 arr에는 도망자의 수 + 나무 (101로 표시) 하여 더해주었다.
• 도망자들은 runner 리스트에 위치와 방향을 따로 관리해주었다.
• runner_move함수
  • 도망자들을 순회하며, 아직 잡히지 않은 도망자인 경우 아래를 수행해준다.
    • 현재 위치가, 술래와 거리가 3 이하인 경우
    • 범위를 벗어난다면 방향을 회전한 후 가야되는 곳을 다시 정의해준다 (ni, nj)
    • 한 칸 이동할 곳이 술래가 아니라면 +1을 해주고 기존 위치에 -1을 해준다.
• catch_move함수
  • 저장해둔 catcher 함수를 언팩해준다.
  • 다음 위치 ni, nj에 저장해주고 cnt += 1을 해준다.
  • 이 때, 방향을 변경해야되는 곳이라면 바로 변경하기 위해 아래 로직을 수행해준다.
  • 만약, go_range => 현재 방향으로 갈 수 있는 최대 수 == cnt라면
    • 만약 reverse가 True인 경우 s가 0인지 체크해준다 (정중앙)
    • 맞다면 d = 0, reverse = False
    • 아니라면 s -= 1, d = (d+3) % 4를 통해 변경
    • 정방향인 경우에도 마찬가지로 수행해준다.
  • catcher를 업데이트 해준 후 현재 칸을 포함해 3칸을 탐색해준다.
    • 만약 arr[si][sj] 가 0보다 크고 101보다 작다면 => 나무가 있으면 못잡으므로
    • remove_cnt에 해당 칸에 존재하던 도망자의 수만큼 추가해주고 arr 값을 0으로 변경해준다.
    • 이후, 도망자들을 순회하며 위치가 현재 잡힌 곳과 같다면 도망자[idx]를 []로 변경해준다.

def runner_move():  
    for idx, r in enumerate(runner):  
        if r:  
            si, sj, d = r  
            if abs(catcher[0] - si) + abs(catcher[1] - sj) <= 3:  
                ni, nj = si + di[d], sj + dj[d]  
                if not (0<=ni<N and 0<=nj<N):  
                    d = (d+2) % 4  
                    ni, nj = si + di[d], sj + dj[d]  
                if not (ni, nj) == (catcher[0], catcher[1]):  
                    arr[ni][nj] += 1  
                    arr[si][sj] -= 1  
                    runner[idx] = [ni, nj, d]  

def catch_move():  
    global catcher  
    i, j, s, d, cnt, reverse = catcher  
    ni, nj = i + di[d], j + dj[d]  
    cnt += 1  
    if cnt == go_range[s]:  
        cnt = 0  
        if reverse:  
            if s == 0:  
                reverse = False  
                d = 0  
            else:  
                s -= 1  
                d = (d+3) % 4  
        else:  
            if s == len(go_range) - 1:  
                reverse = True  
                d = 2  
            else:  
                s += 1  
                d = (d+1) % 4  
    catcher = [ni, nj, s, d, cnt, reverse]  
    remove = 0  
    for re in range(3):  
        si, sj = ni + di[d]*re, nj + dj[d]*re  
        if not (0<=si<N and 0<=sj<N):  
            break  
        if 0 < arr[si][sj] < 101:  
            remove += arr[si][sj]  
            a = arr[si][sj]  
            arr[si][sj] = 0  
            for idx, val in enumerate(runner):  
                if not a:  
                    break  
                if not val:  
                    continue  
                if (si, sj) == (val[0], val[1]):  
                    runner[idx] = []  
                    a-= 1  
    return remove  

N, M, H, K = map(int, input().split())  
catcher = [N//2, N//2, 0, 0, 0, False]  
arr = [[0] * N for _ in range(N)]  
runner = [[] for _ in range(M+1)]  
go_range = [i for i in range(1, N) for _ in range(2)]  
go_range.append(N-1)  

di, dj = [-1, 0, 1, 0], [0, 1, 0, -1]  
for m in range(1, M+1):  
    a, b, c = map(int, input().split())  
    a -= 1  
    b -= 1  
    runner[m] = [a, b, c]  
    arr[a][b] += 1  
for _ in range(H):  
    a, b = map(int, input().split())  
    arr[a-1][b-1] += 101  

result = 0  
for k in range(1, K+1):  
    runner_move()  
    v = catch_move()  
    result += k * v  
print(result)

• 매일 풀다 보니 확실히 조건 정리와 의사 코드를 탄탄히 작성하는 것이 익숙해지고 있다.
• 이번 문제에서 헷갈렸던 부분은 술래와 도망자, 나무가 같은 칸에 있는 경우 어떻게 되는 것인지 고민하였지만 나무와 도망자가 같은 칸에 있다면 숨을 수 있다는 걸 우선 순위로 구현하였다.