[코드트리/삼성SW역량테스트] 술래잡기

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek

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

 

Status : Solved

 

Time : 00:51:25

 

---

 

문제 설명 / 입력 및 출력

 

전체 문제 설명은 코드트리 사이트를 참조해 주세요!

 

---

 

풀이

 

빡구현 문제. 난도가 어렵기보다는, 어떤 케이스를 제대로 구현하지 못했다면 수많은 맞왜틀로 고통받는 타입이다.

 

1. 술래의 움직임 구현에 주의하자. 술래는 총 2*n^2 시간동안의 주기로 같은 장소로 돌아오고 규칙이 일정하다. 따라서 미리 구해놓는 게 포인트이다. (n//2, n//2)에서 시작하는 정방향 루트와 (0, 0)에서 시작하는 역방향 루트를 고려하여 (x, y, dir) 방향을 저장하는 게 포인트이다.

 

2. 도망자들의 움직임 구현은 훨씬 간단한 편이다. 각 도망자가 조건을 만족할 경우 위치를 변환하여 저장하고, 술레가 움직인 후에 술래의 시야 내에 있으면서 나무에 있지 않은 도망자를 배제하면 된다.

 

3. 매우 주의할 점, 삼성은 (r, c) 좌표계를 주면서 (x, y)로 표현한다. 다른 문제를 풀다가 삼성 문제를 풀게 될 때마다 당황하게 되는 포인트...

 

풀이 코드

n, m, h, k = map(int, input().split())
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

runner_list = list()
tagger_moves = list()
sx, sy, sd, sl, smax = n // 2, n // 2, 0, 0, 1


tagger_moves.append([sx, sy, sd])
while (sx, sy) != (0, 0) :
    sx += dx[sd]
    sy += dy[sd]
    sl += 1
    if sl == smax :
        sd = (sd + 1) % 4
        sl = 0
        if sd % 2 == 0 :
            smax += 1
    tagger_moves.append([sx, sy, sd])
tagger_moves.pop()

sx += dx[sd]
sy += dy[sd]
sd = (sd + 2) % 4
sl = 0
while (sx, sy) != (n // 2, n // 2) :
    sx += dx[sd]
    sy += dy[sd]
    sl += 1
    if sl == smax :
        sd = (sd - 1) % 4
        sl = 0
        if sd % 2 == 1 :
            smax -= 1
    tagger_moves.append([sx, sy, sd])
tagger_moves.pop()

for _ in range(m) :
    y, x, d = map(int, input().split())
    runner_list.append([x-1, y-1, d])

is_tree = [[False]*n for _ in range(n)]
for _ in range(h) :
    y, x = map(int, input().split())
    is_tree[y-1][x-1] = True

ans = 0
for i in range(1, k+1) :
    if not runner_list :
        break
    for j in range(len(runner_list)) :
        x, y, d = runner_list[j]
        if abs(sx - x) + abs(sy - y) > 3 :
            continue
        ax, ay = x + dx[d], y + dy[d]
        if not (-1 < ax < n and  -1 < ay < n) :
            d = (d + 2) % 4
            ax, ay = x + dx[d], y + dy[d]
        if (ax, ay) == (sx, sy) :
            continue
        runner_list[j] = [ax, ay, d]
    next_runner_list = list()
    sx, sy, sd = tagger_moves[i % len(tagger_moves)]
    sight_list = [(sx + dx[sd]*l, sy + dy[sd]*l) for l in range(3)]
    for j in range(len(runner_list)) :
        x, y, d = runner_list[j]
        if (x, y) in sight_list and not is_tree[y][x] :
            continue
        next_runner_list.append([x, y, d])
    ans += i * (len(runner_list) - len(next_runner_list))
    runner_list = next_runner_list
    
print(ans)

풀이 완료!