[코드트리/삼성SW역량테스트] 메이즈 러너 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner

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

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 02:41:13

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

빡구현 문제. 구현 자체는 40여분만에 끝났는데, 디버깅에 시간이 너무 오래 걸린다... 복잡한 구조를 구현할 때 좀 더 신경쓰는 편이 좋겠다.

 

주목할 점이라면, 회전에 대한 처리가 될 것이다. 첫번째로, length 범위 내에서 (r, c)를 90도 회전하면  (c, length-r+1)이 된다는 점을 유의하자. 또한 기준 좌표가 0, 0이 아니므로 이 역시 신경써야 한다.

 

두 번째로, 최소 정사각형을 구하는 문제가 있겠다. 맨 처음에는 그리디하게 최소 정사각형이라면 하나 이상의 runner와 출구가 모서리에 반드시 존재해야 한다!고 생각해서 구현했는데, 생각해보면 N <= 10이므로 O(N^3) 시간 내에 완전탐색으로 풀이해도 충분하다.

 

풀이 코드

import sys
input = sys.stdin.readline
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
cvt = lambda x : int(x) - 1

N, M, K = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)]
runners = list()
exit_loc = [-1, -1]
left = M

def distance(a) :
    return abs(a[0] - exit_loc[0]) + abs(a[1] - exit_loc[1])

class Runner() :
    def __init__(self, r, c) :
        self.r = r
        self.c = c
        self.escaped = False
        self.moved = 0
    def move(self) :
        global left
        if self.escaped :
            return
        best_dist, br, bc = distance(self.where()), self.r, self.c
        for i in range(4) :
            ar, ac = self.r + dr[i], self.c + dc[i]
            if -1 < ar < N and -1 < ac < N and maze[ar][ac] == 0 :
                dist = distance([ar, ac])
                if dist < best_dist :
                    best_dist, br, bc = dist, ar, ac
                    break
        if br == self.r and bc == self.c : 
            return
        self.moved += 1
        self.r = br
        self.c = bc
        if exit_loc[0] == self.r and exit_loc[1] == self.c :
            self.escaped = True
            self.r = -1
            self.c = -1
            left -= 1
            return

    def where(self) :
        return [self.r, self.c]

def find_rec() :
    runners_rotated = list()
    for length in range(2, N+1) :
        for sr in range(N-length+1) :
            for sc in range(N-length+1) :
                er = sr + length-1
                ec = sc + length-1
                if not (sr <= exit_loc[0] <= er and sc <= exit_loc[1] <= ec) :
                    continue
                for runner in runners :
                    if sr <= runner.r <= er and sc <= runner.c <= ec and not runner.escaped :
                        runners_rotated.append(runner)
                if runners_rotated :
                    return runners_rotated, (length, sr, sc)

def search_min_rec() :
    runners_rotated, best_priority = find_rec()
    length, r, c = best_priority
    new_maze = [[0]*length for _ in range(length)]
    for i in range(length) :
        for j in range(length) :
            new_maze[j][length-i-1] = max(0, maze[r+i][c+j] - 1)

    for i in range(length) :
        for j in range(length) :
            maze[r+i][c+j] = new_maze[i][j]
    for runner in runners_rotated :
        runner.r, runner.c = runner.c - c + r, length - (runner.r - r) - 1 + c 
    exit_loc[0], exit_loc[1] = exit_loc[1] - c + r, length - (exit_loc[0] - r) - 1 + c
    
for _ in range(M) :
    r, c = map(cvt, input().split())
    runners.append(Runner(r, c))
exit_loc = list(map(cvt, input().split()))

for i in range(1, K+1) :
    for runner in runners :
        runner.move()
    if not left :
        break
    search_min_rec()

ans = 0
for runner in runners :
    ans += runner.moved
print(ans)
print(*[i + 1 for i in exit_loc])

풀이 완료!