[CodeTree] 술래잡기 - 삼성 SW 역량테스트 2022 상반기 오전 1번 문제

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

 

문제 분석

• NxN 크기의 격자에서 정중앙에 위치해 있는 술래 1명과, 도망자 M명이 술래잡기 게임을 진행함.
• M명의 도망자는 상-하 혹은 좌-우로만 이동이 가능한 2가지 Type이 존재하며, 처음에는 항상 오른쪽 혹은 아래쪽을 보며 술래잡기 게임을 시작함.
• 격자 내 H개의 나무가 존재하는데, 도망자가 나무가 있는 격자 위치로 이동한다면 술래는 도망자를 잡지 못함.
• 도망자 이동
  
  • 술래와의 유클리디언 거리가 3이하인 도망자만 이동 수행.
  • 현재 바라보고 있는 방향으로 1칸 이동할 때 격자 내 위치라면, 술래가 없다면 이동, 술래가 있다면 이동하지 않음.
  • 현재 바라보고 있는 방향으로 1칸 이동할 때 격자를 벗어난다면, 현재 방향의 반대 방향으로 회전한 후 술래가 없다면 이동, 술래가 있으면 이동하지 않음.
• 술래 이동
  • 술래는 문제에서 주어진 회전 회오리 방향에 맞게 (N//2, N//2) -> (0, 0)으로 이동.
  • (0, 0)에 도착하면 다시 왔던 방향대로 되돌아가며 (N//2, N//2) 좌표로 이동.
  • 만약 이동하려는 위치가 방향이 틀어지는 지점일 경우, 방향을 바로 틀어주는 행위를 수행함.
  • 위 과정을 K번 동안 반복적으로 수행함.
• 술래 잡기
  • 술래가 바라보는 방향에서 현재 위치 포함 3칸 범위내에 존재하는 도망자를 잡는 행위를 수행함.
  • 이동하려는 위치가 나무에 가려져있다면, 도망자를 잡지 못함.
  • 도망자를 잡을 경우, (현재 Turn * 잡은 도망자 수)만큼 Score를 얻음.
• (도망자 이동 -> 술래 이동) 과정을 총 K번 수행한 후, 술래가 얻은 최종 Score를 Return하는 문제.

 

문제 접근

• 초기화 단계
  • 한 칸에 여러 도망자가 위치할 수 있기에 defaultdict(list)를 활용하여 (tx, ty)를 key로, 도망자의 방향을 Value로 하는 딕셔너리 생성.
  • 특정 격자에 나무가 존재하는지를 판단하기 위해 set() 자료구조 활용.
  • 문제에서 주어진 술래 이동 방향을 저장하기 위한 초기화 과정을 수행하면, 왕복 거리는 총 ((N**2)-1)*2의 길이를 가지게 됨. 따라서, 만약 반복 진행하려는 횟수 K에 맞게 divmod()를 활용하여 길이를 맞춰줌.
• 도망자 이동
  • 이동 가능한 도망자가 순차적으로 이동하는 것이 아닌 동시에 모든 이동이 수행되기 때문에, 이를 관리하기 위해 시작 시 도망자의 위치를 저장한 딕셔너리를 copy하여 관리.
  • 유클리디언 거리 3 이내에 존재하는 도망자 추출.
  • 도망자의 다음 칸이 격자를 벗어나지 않을 경우, 술래가 있을 때는 (cur_x, cur_y, cur_d)를 복사한 딕셔너리에 저장하고, 술래가 없을 경우 (next_x, next_y, cur_d)를 딕셔너리에 저장.
  • 도망자의 다음 칸이 격자를 벗어날 경우 반대 방향으로 회전을 수행하고, 술래가 있을 때는 (cur_x, cur_y, 변경된 방향)을 복사한 딕셔너리에 저장하고, 술래가 없을 경우 (next_x, next_y, 변경된 방향)을 딕셔너리에 저장.
• 술래 이동 / 술래 잡기
  • 초기에 정의한 술래 이동 위치 list에 따라 이동 수행.
  • 현재 지점을 포함하여 술래가 바라보는 위치로 3칸 탐색 수행
  • 도망자가 있을 때, 나무가 있으면 pass, 나무가 없다면 도망자를 잡음.
  • 남아있는 도망자가 존재하지 않는다면, 더 이상 탐색할 필요가 없기 때문에 종료하는 조건 추가.
• 도망자를 잡고 합산한 최종 Score를 Return 한 후 종료.

 

소스 코드

# define lib
from copy import deepcopy
from collections import deque, defaultdict

# set value from input
n, m, h, k = map(int, input().split())
runner, trees = defaultdict(list), set()
d_to_pos = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
for _ in range(m):
    x, y, d = map(int, input().split())
    runner[(x-1, y-1)].append(d)

for _ in range(h):
    x, y = map(int, input().split())
    trees.add((x-1, y-1))

# set chaser info
chase_x, chase_y, c_length = n//2, n//2, (n**2)-1
c_movement = [idx for idx in range(1, n) for _ in range(2)] + [n-1]
chaser_pos, chase_idx = [], 0

tx, ty, td = n//2, n//2, 0
for cd in c_movement:
    while cd > 0:
        tx, ty = tx+d_to_pos[td][0], ty+d_to_pos[td][1]
        if cd == 1:
            chaser_pos.append((tx, ty, (td+1)%4))
        else:
            chaser_pos.append((tx, ty, td))
        cd -= 1
    td = (td+1)%4
chaser_pos.pop()
chaser_pos.append((0, 0, 2))

tx, ty, td = 0, 0, 2
for cd in c_movement[::-1]:
    while cd > 0:
        tx, ty = tx+d_to_pos[td][0], ty+d_to_pos[td][1]
        if cd == 1:
            chaser_pos.append((tx, ty, (td-1)%4))
        else:
            chaser_pos.append((tx, ty, td))
        cd -= 1
    td = (td-1)%4
chaser_pos.pop()
chaser_pos.append((n//2, n//2, 0))

quote, remain = divmod(k, c_length*2)
chaser_pos = chaser_pos * quote + chaser_pos[:remain]

# run k turn
turn, score = 0, 0
while turn < k:
    # find which distance under 3
    candits = []
    new_runner = deepcopy(runner)
    for (rx, ry), values in runner.items():
        if (abs(chase_x-rx) + abs(chase_y-ry)) > 3:
            continue
        candits.append((rx, ry))
        del new_runner[(rx, ry)]
    
    for (rx, ry) in candits:
        for rd in runner[(rx, ry)]:
            nrx, nry = rx+d_to_pos[rd][0], ry+d_to_pos[rd][1]
            if nrx < 0 or nrx >= n or nry < 0 or nry >= n:
                nrd = (0 if rd == 2 else 2) if rd in [0, 2] else (3 if rd == 1 else 1)
                nrx, nry = rx+d_to_pos[nrd][0], ry+d_to_pos[nrd][1]
                if (nrx, nry) != (chase_x, chase_y):
                    new_runner[(nrx, nry)].append(nrd)
                else:
                    new_runner[(rx, ry)].append(nrd)
            else:
                if (nrx, nry) == (chase_x, chase_y):
                    new_runner[(rx, ry)].append(rd)
                else:
                    new_runner[(nrx, nry)].append(rd)

    # chaser move
    n_chase_x, n_chase_y, n_chase_d = chaser_pos[chase_idx]
    candits = [
        (n_chase_x, n_chase_y),
        (n_chase_x+d_to_pos[n_chase_d][0], n_chase_y+d_to_pos[n_chase_d][1]),
        (n_chase_x+d_to_pos[n_chase_d][0]*2, n_chase_y+d_to_pos[n_chase_d][1]*2),
    ]
    
    for cx, cy in candits:
        if cx < 0 or cx >= n or cy < 0 or cy >= n:
            break
        if new_runner.get((cx, cy), -1) != -1:
            if (cx, cy) not in trees:
                score += len(new_runner[(cx, cy)]) * (turn+1)
                del new_runner[(cx, cy)]

    if len(new_runner) == 0:
        break

    runner = new_runner
    chase_x, chase_y = n_chase_x, n_chase_y
    turn, chase_idx = turn+1, chase_idx+1

print(score)

• 제출 횟수: 2회 (최초 제출 시, 이동과 동시에 술래의 방향을 갱신하는 과정을 스킵함)
• 풀이 시간: 80분