[코드트리 챌린지] 1주차 - 메이즈러너

1주차 첫 진단 결과!

 

문제 풀이

 

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

삼성 기출 문제 풀이

1초 동안, 이동 및 회전이 일어남.

1. 참여자 동시에 모두 이동

2. 출구와 최소 참여자1명 포함하는 가장 작은 정사각형 부분 회전. 회전시, 벽 내구도 -1.

3. k초동안 또는 그 전에 모두가 탈출 했다면, 총 이동거리와 출구의 좌표를 출력.

** 좌표는 (1,1)부터 시작이므로, 0,0으로 변경해서 쓴다면 정답 출력시 유의.

import copy
n,m,k = map(int,input().split())
g = []
for _ in range(n):
    g.append(list(map(int,input().split())))
people = {}
for i in range(1,m+1):
    a,b= map(int,input().split())
    people[i] = [a-1,b-1]
ex,ey = map(int,input().split())
ex -= 1
ey -=1

total = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def move():# 참여자 동시에 이동
    global people, total
    newPeople = {}
    for p in people:
        x,y = people[p]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and g[nx][ny] ==0:
                
                if abs(nx-ex)+abs(ny-ey) < abs(x-ex)+abs(y-ey):# 더 탈출구와 가깝다면 이동.
                    total += 1
                    if not (nx == ex and ny == ey):
                        newPeople[p] = [nx,ny]
                    break
        else:# 이동 불가하면 그대로.
            newPeople[p] = [x,y]
    people = newPeople# 참여자 정보 업데이트


def makeSquare():# 가장 작은 정사각형 만들기(길이가 작고, 가장 왼쪽 위 좌표가 행이 작고, 열이 작은 순)
    
    for length in range(2,n+1):
        for i in range(n):
            for j in range(n):
                    if i+length <= n and j+length <= n:
                        for p in people:
                            x,y = people[p]
                            if i <= x <i+length and j <= y <j + length:
                                if i <= ex <i+length and j <= ey <j + length:
                                    return [i,j,length]
    

def rotate(x,y,length):# x,y 시작점, 길이가 length인 정사각형 모양부분 회전.
    global g,people,ex,ey

    tmp = copy.deepcopy(g)
    newPeople = {}
    flag = False
    for i in range(length):
        for j in range(length):
            px,py = i+x,j+y 
            nx,ny = j+x,length-1-i+y
            tmp[nx][ny] = g[px][py]
            if tmp[nx][ny] > 0:
                tmp[nx][ny] -= 1
            for p in people:# 참여자 회전.
                a,b = people[p]
                if a==px and b == py:
                    newPeople[p] = [nx,ny]
            
            if not flag and ex == px and ey == py:# 탈출구 옮기기.(한번 옮기고 다시 또 옮겨질 것에 유의해서 flag사용)
                ex,ey = nx,ny
                flag = True
    for p in people:# 정사각형 내에 해당하지 않는 참가자 새로운 참여자 딕셔너리로 옮기기.
        a,b = people[p]
        if not (x <= a < x+length and y <= b < y+length):
            newPeople[p] = [a,b]
      
    g = tmp
    people = newPeople


for t in range(1,k+1):

    move()
    if len(people) == 0: # 이전에 모두가 탈출해서 끝난다면 break
        break
    x,y,length = makeSquare() # 가장 작은 정사각형 찾기
    rotate(x,y,length)# 회전하기.
    
    
print(total)
print(ex+1,ey+1)

 

** 코드 짜면서 유의할점!

회전 부분에서 이미 회전한 탈출구 좌표가 또 다시 회전 될 수 있으므로, flag를 사용함.

이미 모두가 탈출했을 때 , break가 되도록 유의.