[코드트리] 메이즈 러너

문제 링크

메이즈 러너

구현 방식

• persons는 [[x, y], [x, y] ... ]형식, exit는 [x, y] 형식으로 관리해주었다
• board는 exit만 -1로 표기해주고, 나머지는 그대로 받아주었다

참가자 이동

• 문제의 조건에 맞게 참가자가 한칸씩 이동하는 기능
• 상하방향을 우선시하기 때문에 dx = (-1, 1, 0, 0)으로 선언해줌
• flag보다 출구~이동한위치의 거리가 짧아진다면 참가자를 이동시킴
  -> 이 때 참가자가 한 번 이동했다면 break 해줘야함
• 참가자들을 모두 이동시킨 후에, while문을 돌면서 persons에 출구의 좌표가 남아있지 않을 때까지 persons.remove([exit[0], exit[1]])을 수행해주었다

가장 작은 정사각형 찾기

• persons를 순회하면서, Square list를 완성해준다
  • minX, minY, maxX, maxY를 구하고, diff = width - height 값이 0이라면 바로 Square에 append
  • diff가 양수라면 x방향을 늘려야하므로 abs(diff)만큼 for문을 돌면서 minX가 0보다 클때 동안 minX -=1 수행, 만약 minX가 0이 된다면 maxX +=1 수행
  • diff가 음수라면 y방향을 늘려야하므로 abs(diff)만큼 for문을 돌면서 minY가 0보다 클때동안 minY -=1 수행, 만약 minY가 0이 된다면 maxY +=1 수행
  • Square에 append할 때에는 (manX-minX, minX, minY, maxX, maxY) 형식으로 넣어서 문제의 조건대로 sorting이 가능하도록 해줬다
• 완성된 Square를 sorting하여 구한 Square[0][1:]가 찾고자하는 가장 작은 정사각형이 된다

시계방향 90도 회전

• 이 부분은 board를 회전해주고, persons를 따로 회전해주는 방식으로 구현해주었다
• 시계방향 90도 회전 공식은 아래와 같다

A = reversed(A); A = list(map(list, zip(*A)))

• 회전할 때, 내구도 -1을 수행해줘야한다. 또한, sqr[i-minX][j-minY]가 -1이라면, exit을 [i, j]로 갱신해주어야한다

코드

import sys

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

N, M, K = map(int, sys.stdin.readline()[:-1].split())
board = [list(map(int, sys.stdin.readline()[:-1].split())) for n in range(N)]
persons = []
for m in range(M): tmp = list(map(int, sys.stdin.readline()[:-1].split())); tmp[0]-=1; tmp[1]-=1; persons.append(tmp)
exit = list(map(int, sys.stdin.readline().split())); exit[0]-=1; exit[1]-=1; board[exit[0]][exit[1]] = -1

answer_move = 0
for k in range(K):
    
    ##### 참가자 이동
    person_exited = []
    for m in range(len(persons)):
        x, y = persons[m]
        flag = abs(x-exit[0]) + abs(y-exit[1])
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if board[nx][ny] == 0 or board[nx][ny] == -1:
                    if abs(nx-exit[0]) + abs(ny-exit[1]) < flag:
                        answer_move += 1
                        persons[m] = [nx, ny]
                        break #break 필수!
    while True:
        if [exit[0], exit[1]] not in persons: break
        else: persons.remove([exit[0], exit[1]])
    if len(persons) == 0: break ##### 모든 참가자가 탈출 성공
                    
    ##### 가장 작은 정사각형 찾기
    ex, ey = exit[0], exit[1]
    Square = []
    for m in range(len(persons)):
        x, y = persons[m]
        minX = min(x, ex); minY = min(y, ey); maxX = max(x, ex); maxY = max(y, ey)
        width = maxY - minY; height = maxX - minX; diff = width - height
        if diff == 0: Square.append((maxX-minX, minX, minY, maxX, maxY)); continue
        elif diff > 0: #x방향 늘려야함
            for i in range(abs(diff)):
                if 0 < minX: minX -= 1
                else: maxX += 1
        else: #y방향 늘려야함
            for i in range(abs(diff)):
                if 0 < minY: minY -= 1
                else: maxY += 1
        Square.append((maxX-minX, minX, minY, maxX, maxY))
    Square.sort()
    minX, minY, maxX, maxY = Square[0][1:]

    ##### 시계방향 90도 회전
    S = maxY-minY+1
    sqr = [[0]*S for s in range(S)]
    for i in range(minX, maxX+1):
        for j in range(minY, maxY+1):
            sqr[i-minX][j-minY] = board[i][j]

    for m in range(len(persons)): #person 위치 회전
        x, y = persons[m]
        if minX <= x <= maxX and minY <= y <= maxY:
            tmp = [[0]*S for s in range(S)]; tmp[x-minX][y-minY] = 1
            tmp = reversed(tmp); tmp = list(map(list, zip(*tmp)))
            for i in range(minX, maxX+1):
                for j in range(minY, maxY+1):
                    if tmp[i-minX][j-minY] == 1: persons[m] = [i, j]

    sqr = reversed(sqr); sqr = list(map(list, zip(*sqr)))
    for i in range(minX, maxX+1):
        for j in range(minY, maxY+1):
            if sqr[i-minX][j-minY] >= 1:
                board[i][j] = sqr[i-minX][j-minY] - 1
            elif sqr[i-minX][j-minY] == -1:
                board[i][j] = -1
                exit = [i, j]
            else:
                board[i][j] = 0

print(answer_move); print(exit[0]+1, exit[1]+1)

24.04.10 update

import sys
import heapq
input = sys.stdin.readline

dx = (1, -1, 0, 0)
dy = (0, 0, -1, 1)

def move():
    global total_move

    for p in range(len(person)):
        x, y = person[p]
        cur_di = abs(exit[0]-x)+abs(exit[1]-y)
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if board[nx][ny] == 0 or board[nx][ny] == -1:
                    nex_di = abs(exit[0]-nx)+abs(exit[1]-ny)
                    if cur_di > nex_di:
                        person[p] = [nx, ny]
                        total_move += 1
                        break
    
def escape():
    while exit in person: person.remove(exit)

def rotate():
    global exit

    ##### 가장 작은 정사각형 잡기
    square = []; ex, ey = exit
    for p in range(len(person)):
        x, y = person[p]
        minX=min(x, ex); maxX=max(x, ex); minY=min(y, ey); maxY=max(y, ey)
        h = maxX-minX+1; w = maxY-minY+1; diff = h-w
        if diff == 0: heapq.heappush(square, (h, minX, minY))
        elif diff > 0: #width 늘려서 정사각형 만들어야함
            for i in range(abs(diff)):
                if minY > 0: minY -= 1
                else: maxY += 1
            heapq.heappush(square, (h, minX, minY))
        else: #height 늘려서 정사각형 만들어야함
            for i in range(abs(diff)):
                if minX > 0: minX -= 1
                else: maxX += 1
            heapq.heappush(square, (w, minX, minY))
    size, sx, sy = heapq.heappop(square)
    ex = sx+size-1; ey = sy+size-1 

    ##### board 시계 방향 90도 회전
    box = [[0]*size for s in range(size)]
    for x in range(sx, ex+1):
        for y in range(sy, ey+1):
            box[x-sx][y-sy] = board[x][y]
    box = reversed(box); box = list(map(list, zip(*box)))
    for x in range(sx, ex+1):
        for y in range(sy, ey+1):
            if box[x-sx][y-sy] >= 1: board[x][y] = box[x-sx][y-sy]-1
            elif box[x-sx][y-sy] == -1: board[x][y] = -1; exit = [x, y]
            else: board[x][y] = 0
    
    ##### person 시계 방향 90도 회전
    for p in range(len(person)):
        x, y = person[p]
        if sx <= x <= ex and sy <= y <= ey:
            tmp = [[0]*size for s in range(size)]; tmp[x-sx][y-sy] = 1
            tmp = reversed(tmp); tmp = list(map(list, zip(*tmp)))
            for i in range(size):
                for j in range(size):
                    if tmp[i][j] == 1: person[p] = [i+sx, j+sy]; break


N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for n in range(N)]
person = []
for m in range(M):
    tmp = list(map(int, input().split())); tmp[0]-=1; tmp[1]-=1; person.append(tmp)
exit = list(map(int, input().split())); exit[0]-=1; exit[1]-=1; board[exit[0]][exit[1]] = -1

total_move = 0
for k in range(K):
    move()
    escape()
    if len(person) == 0: break
    rotate()
print(total_move)
print(exit[0]+1, exit[1]+1)