메이즈 러너 [삼성 기출]

1. 문제 접근 방법

- 포기하지 않는 자세와 테스트 케이스를 직접 만드는 것의 중요성을 알려준 문제이다.

-> 디버깅이 안되면 테스트 케이스를 직접 만들어야 한다 

-> 실제 제출하기 전에 테스트 케이스를 최대한 여러 개 만들어서 돌려보는 편이 매우 좋다. 

 

- 사람이 탈출하는 경우를 중간에 고려하다보니, 중간 중간에 코드를 수정해야 하는 일이 있었다.

-> 미리 코드 설계를 다 하고 나서, 그 다음에 코드를 작성하는 편이 좋을까?

-> 문제 풀이 전략에 대해 고민해봐야겠다. 

 

- rotate는 매우 중요하다.

-> rotate를 최근에 학습한 방법을 적용했는데, 에러가 발생했다.

-> 또한, rotate를 할 때도, 길이를 잘라서 rotate해야 한다는 점도 기억해야 한다.

-> 그리고 중요한 점은 그냥 행을 잘라서, 해당 열의 위치에 넣어주는 식으로 하는 편이 좋다는 점이다. 

 

- 또한, len이라는 변수를 활용하는데도 주의해야 한다.

-> 함부로 활용하면 이것이 문법 에러를 발생시킬 수 있다.

-> 최대한 활용하지 않는 편이 좋다. 

 

- 사람과 탈출구에 대한 이동과, 벽들의 이동을 분리한 것이 좋았다.

-> 사람과 탈출구에 대한 이동을 더 좋게할 수 있는 방법이 있을지 찾아봐야겠다. 

 

- 전부 탈출했는지 확인하는 시점은, 사람이 탈출하고 난 후여야 한다는 점을 반드시 기억해야 한다.

-> 왜냐하면 그렇게 하지 않으면, 다 사람이 탈출하고 나서 가장 작은 square를 찾으려고 하면 에러가 나기 때문이다. 

 

- 중간에 코드를 수정할 때, 특히 for문의 변수명 같은 것을 특히 주의해야 한다.

-> 이러한 부분은 매우 실수하기 쉬운 부분이다. 

 

 

 

2. 코드

import copy 

N, M, K = map(int, input().split())

board = [] 

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

for i in range(N):
    row = list(map(int, input().split()))
    board.append(row)
    
    
    
people = []
totalMove = 0 

exit = [False]*M 

for i in range(M):
    a, b = map(int, input().split())
    people.append([a-1, b-1])


ox, oy = map(int, input().split()) 
ox -= 1
oy -= 1 

## 사람들을 이동시키는 함수
## 사람들을 한 명씩 순차적으로, 이동시키되, 
## 탈출을 만나면 바로 탈출시킨다. 
## 한 번 탈출한 사람은 이동시키지 않는다. 
def movePeople():
    
    
    global totalMove 
    
     
    ## people 배열을 탐색한다. 
    for i in range(len(people)):
        if exit[i] == True:
            continue
        
        move = 0
        
        x = people[i][0]
        y = people[i][1] 
        
        ## 탈출구까지의 거리를 계산한다 
        currDist = abs(x-ox)+abs(y-oy)
        
        nextMove = False
        
        ## 4방향에 대해서 움직였을 때, 
        ## 현재 거리(탈출구까지의 거리)보다 작아지는지 확인한다.
        ## 이 때, 이동하는 과정에서 탈출구를 만나면 바로 탈출시킨다. 
        ## 단, move의 카운트는 세줘야 한다. 
        for j in range(4):
            nx = x + dx[j]
            ny = y + dy[j]
            
            ## board안에 있고, 빈 칸일때만 이동 가능하다. 
            if 0<=nx and nx < N and 0<=ny and ny<N and board[nx][ny] == 0:
                
                nextDist = abs(nx-ox)+abs(ny-oy)
                
                if nx == ox and ny == oy:
                    exit[i] = True
                    move = 1 
                    break
                
                ## move를 중복하지 않도록 nextMove라는 변수로 중복을 방지하였다. 
                if nextMove == False and currDist > nextDist:
                    people[i][0] = nx
                    people[i][1] = ny
                    move = 1 
                    nextMove = True

        ## totalMove에 move를 더해준다. 
        ## 이 때, move를 중복해서 세지 않도록 주의해야 한다. 
        totalMove += move 
        

## 가장 작은 정사각형을 찾는 함수 
def findSmallestSquare():
    

    ## 정사각형의 변의 길이를 1부터 N까지 늘려주면서, 탐색한다
    ## 하나라도 맞는 케이스가 나오면, 바로 해당 sx,sy,ex,ey 좌표를 리턴시킨다. 
    ## 정사각형의 네 점을 찾는 것이 목표이다. 
    ## for문의 변수명으로 len과 같은 것은 쓰지 않도록 주의한다. 
    for k in range(1, N+1):
        for i in range(0, N-k+1):
            for j in range(0, N-k+1):
                
                sx = i
                sy = j
                ex = i+k-1
                ey = j+k-1
                
                ## 탈출문이 현재 내가 설정한 sx,sy,ex,ey 내부에 있을 때, 
                if sx<= ox and ox <=ex and sy<= oy and oy <= ey:
                    ## 마찬가지로 for문의 변수명을 주의한다 
                    ## 탈출하지 않은 사람중에서 한 사람이라도 구간 내에 있다면
                    ## 유효하므로 바로 리턴한다. 
                    for l in range(len(people)):
                        if exit[l] == True:
                            continue
                        
                        x = people[l][0]
                        y = people[l][1] 
                    
                        if sx<= x and x <= ex and sy <= y and y <= ey:
                            return [sx, sy, ex, ey]
             
    
## square를 rotate 시킨다
def rotate(square):
    
    
    ## print("square는?")
    ## print(square)
    
    ## tmpBoard를 만들어준다. 
    tmpBoard = copy.deepcopy(board)
    
    ## square의 sx, sy, ex, ey 네 점을 변수에 저장한다. 
    sx = square[0]
    sy = square[1]
    ex = square[2]
    ey = square[3] 
    
    
    squareLen = ex-sx+1 
    col = ey 
    
    
    ## 행을 row라는 리스트에 담은 다음에
    ## 해당하는 열에 하나씩 담아준다. 
    for i in range(sx, ex+1):
        
        row = board[i][sy:ey+1]
        pos = 0 
        
        for j in range(sx, ex+1):
            tmpBoard[j][col] = row[pos]
            pos += 1 
            
        col -= 1 
            
            
    ## tmpBoard를 내가 변경한 구간만,
    ## board에 업데이트해준다. 
    for i in range(sx, ex+1):
        for j in range(sy, ey+1):
            board[i][j] = tmpBoard[i][j] 
            
            
  
    
    
## 사람과 탈출구를 rotate하기 위한 함수이다. 
def rotatePeopleAndOut(square):
    
    
    global ox
    global oy
    
    global people 
    
    tmpBoard = copy.deepcopy(board)
    initBoard = copy.deepcopy(board)
    
    sx = square[0]
    sy = square[1]
    ex = square[2]
    ey = square[3]
    
    
    ## initBoard에 해당 구간에 있는 사람을 
    ## 숫자로 만들어서 넣어준다. 
    for i in range(len(people)):
        if exit[i] == True:
            continue
        
        x = people[i][0]
        y = people[i][1] 
    
        if sx<= x and x <= ex and sy <= y and y<=ey:
            num = 100*(x+1)+y+1
            initBoard[x][y] = num

    oNum = 100*(ox+1)+oy+1
    initBoard[ox][oy] = oNum
    
    squareLen = ex-sx+1 
   
    col = ey 
    
    ## 마찬가지로 initBoard의 행을 90도 변환시켜서
    ## tmpBoard에 업데이트해준다. 
    for i in range(sx, ex+1):
        
        row = initBoard[i][sy:ey+1]
        
        pos = 0 
        
        for j in range(sx, ex+1):
            tmpBoard[j][col] = row[pos]
            pos += 1 
            
        col -= 1 
   
   

   
    ## people에 있는 값들 중에서
    ## tmpBoard에 업데이트되어 있는 값들을 찾아서, 
    ## 일치한다면, 해당 위치로, people의 인덱스를 바꿔준다.
    ## 이렇게 함으로써, people은 board에 따로 표시하지 않고도 
    ## 위치를 바꿔줄 수 있다. 
    for i in range(len(people)):
        if exit[i] == True:
            continue 
        
        x = people[i][0]
        y = people[i][1]
        
        if sx<=x and x <= ex and sy<=y and y <= ey:
            num = 100*(x+1)+y+1 
            
            for j in range(0, N):
                for k in range(0, N):
                    if tmpBoard[j][k] == num:
                        people[i][0] = j
                        people[i][1] = k
    
    
    ## 마찬가지로 탈출구도 같은 방식으로 정보를 업데이트한다.  
    for i in range(0, N):
        for j in range(0, N):
            if tmpBoard[i][j] == oNum:
                ox = i
                oy = j 
                
            
            
## 벽을 1만큼 부수는 함수
## 해당하는 범위에서 벽이 있다면, 1씩 부숴준다. 
def breakWall(square):
    
    sx = square[0]
    sy = square[1]
    ex = square[2]
    ey = square[3]
    
    
    for i in range(sx, ex+1):
        for j in range(sy, ey+1):
            if board[i][j] > 0:
                board[i][j] -= 1 
    
    
            
    
time = 0 
    
while True:     
    
    ## 시간을 1 증가시킨다.
    ## 시간을 선제적으로 증가시키는 것이 필요하다.
    ## 왜냐하면 그래야 중간에 break문을 할 때, 시간이 제대로 나오기 때문이다. 
    time +=1 
    
    ## 사람들을 이동시킨다. 
    movePeople()     
    
    cnt = 0 
    
    for i in range(len(people)):
        if exit[i] == True:
            cnt += 1 
    
    ## 모든 사람이 탈출했다면, 바로 break해주는 것이 중요하다. 
    ## 여기서 break하지 않으면, findSmallestSquare에서 오류가 발생한다. 
    if cnt == len(people):
        break 
    
                
    square = findSmallestSquare()
    
    rotate(square)
    
    rotatePeopleAndOut(square)
    
    
    breakWall(square) 
  
    
    ## 시간이 K에 도달하면 바로 break해준다.      
    if time == K:
        break
    
    
    
print(totalMove)
print(ox+1, oy+1)

 

3. 참고 코드

n, m, k = tuple(map(int, input().split()))
# 모든 벽들의 상태를 관리한다. 
board = [
    [0] * (n + 1)
    for _ in range(n + 1)
]

for i in range(1, n + 1):
    board[i] = [0] + list(map(int, input().split()))

# 회전의 구현을 편리하게 하기 위해 2차원 배열을 만들어준다. 
next_board = [
    [0] * (n + 1)
    for _ in range(n + 1)
]

# 참가자의 위치 정보를 기록해줍니다.
traveler = [(-1, -1)] + [
    tuple(map(int, input().split()))
    for _ in range(m)
]

# 출구의 위치 정보를 기록합니다. 
exits = tuple(map(int, input().split()))

# 정답(모든 참가자들의 이동 거리 합)을 기록해줍니다.
ans = 0

# 회전해야 하는 최소 정사각형을 찾아 기록해줍니다.
sx, sy, square_size = 0, 0, 0


# 모든 참가자를 이동시킵니다. 
def move_all_traveler():
    global exits, ans

    # m명의 모든 참가자들에 대해 이동을 진행합니다.
    for i in range(1, m + 1):
        # 이미 출구에 있는 경우 스킵합니다.
        if traveler[i] == exits:
            continue
        
        tx, ty = traveler[i]
        ex, ey = exits

        # 행이 다른 경우 행을 이동시켜봅니다.
        if tx != ex:
            nx, ny = tx, ty

            if ex > nx: 
                nx += 1
            else:
                nx -= 1

            # 벽이 없다면 행을 이동시킬 수 있습니다.
            # 이 경우 행을 이동시키고 바로 다음 참가자로 넘어갑니다.
            if not board[nx][ny]:
                traveler[i] = (nx, ny)
                ans += 1
                continue

        # 열이 다른 경우 열을 이동시켜봅니다.
        if ty != ey:
            nx, ny = tx, ty

            if ey > ny: 
                ny += 1
            else:
                ny -= 1

            # 벽이 없다면 행을 이동시킬 수 있습니다.
            # 이 경우 열을 이동시킵니다.
            if not board[nx][ny]:
                traveler[i] = (nx, ny)
                ans += 1
                continue


# 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 찾습니다.
def find_minimum_square():
    global exits, sx, sy, square_size
    ex, ey = exits

    # 가장 작은 사각형부터 모든 사각형을 만들어봅니다. .
    for sz in range(2, n + 1):
        # 가장 좌상단 좌표 r이 작은 것부터 하나씩 만들어봅니다.
        for x1 in range(1, n - sz + 2):
            # 가장 좌상단 좌표 c가 작은 것부터 하나씩 만들어봅니다.
            for y1 in range(1, n - sz + 2):
                x2, y2 = x1 + sz - 1, y1 + sz - 1

                # 만약 출구가 해당 정사각형 안에 없다면 스킵합니다. 
                if not (x1 <= ex and ex <= x2 and y1 <= ey and ey <= y2):
                    continue

                # 한 명 이상의 참가자가 해당 정사각형 안에 있는지 판단합니다.
                is_traveler_in = False
                for l in range(1, m + 1):
                    tx, ty = traveler[l]
                    if x1 <= tx and tx <= x2 and y1 <= ty and ty <= y2:
                        # 출구에 있는 참가자는 제외합니다.
                        if not (tx == ex and ty == ey):
                            is_traveler_in = True

                # 만약 한 명 이상의 참가자가 있다면,
                # 정보를 업데이트합니다. 
                if is_traveler_in:
                    sx = x1
                    sy = y1
                    square_size = sz

                    return


# 정사각형 내부의 벽을 회전시킵니다.
def rotate_square():
    # 우선 정사각형 안에 있는 벽들을 1 감소시킵니다.
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            if board[x][y]: 
                board[x][y] -= 1

    # 정사각형을 시계방향으로 90' 회전합니다.
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            ox, oy = x - sx, y - sy
            # Step 2. 변환된 상태에서 90도 회전시킵니다. 
            rx, ry = oy, square_size - ox - 1
            # Step 3. 다시 (sx, sy)를 더해줍니다. 
            next_board[rx + sx][ry + sy] = board[x][y]

    # next_board 값을 현재 board에 옮겨줍니다.  
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            board[x][y] = next_board[x][y]


# 모든 참가자들 및 출구를 회전시킵니다.
def rotate_traveler_and_exit():
    global exits

    # m명의 참가자들을 모두 확인합니다.
    for i in range(1, m + 1):
        tx, ty = traveler[i]
        # 해당 참가자가 정사각형 안에 포함되어 있을 때에만 회전시킵니다. 
        if sx <= tx and tx < sx + square_size and sy <= ty and ty < sy + square_size:
            # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            ox, oy = tx - sx, ty - sy
            # Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) . (y, square_n - x - 1)가 됩니다.
            rx, ry = oy, square_size - ox - 1
            # Step 3. 다시 (sx, sy)를 더해줍니다.
            traveler[i] = (rx + sx, ry + sy)

    # 출구에도 회전을 진행합니다.
    ex, ey = exits
    if sx <= ex and ex < sx + square_size and sy <= ey and ey < sy + square_size:
        # Step 1. (sx, sy)를 (0, 0)으로 옮기는 변환을 진행합니다.  
        ox, oy = ex - sx, ey - sy
        # Step 2. 변환된 상태에서는 회전 이후의 좌표가 
        #(x,y) -> (y-square_n-x-1)이 됩니다.
        rx, ry = oy, square_size - ox - 1
        # Step 3. 다시 (sx, sy)를 더해줍니다. 
        exits = (rx + sx, ry + sy)


for _ in range(k):
    # 모든 참가자를 이동시킵니다. 
    move_all_traveler()

    # 모든 사람이 출구로 탈출했는지 판단합니다.
    is_all_escaped = True
    for i in range(1, m + 1):
        if traveler[i] != exits:
            is_all_escaped = False

    # 만약 모든 사람이 출구로 탈출했으면 바로 종료합니다.
    if is_all_escaped: 
        break

    # 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 찾습니다.
    find_minimum_square()

    # 정사각형 내부의 벽을 회전시킵니다.
    rotate_square()
    # 모든 참가자들 및 출구를 회전시킵니다.
    rotate_traveler_and_exit()

print(ans)

ex, ey = exits
print(ex, ey)