[코드트리 챌린지] 메이즈 러너

문제

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text 

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

 

 

풀이 해설 & 느낀 점

삼성 2023년 상반기 기출문제 1번 - 메이즈 러너이다.

삼성 문제를 처음 풀어본 것 같은데 이렇게 많은 조건과 함수가 필요한 구현 문제는 처음이었다. 😂

풀면서 머리가 복잡해지고 주춤거리게 되는데, 이럴수록 설계를 체계적으로 꼼꼼하게 해야 될 것 같다.

 

해설은 류호석 님의 삼성 풀이 해몽을 참고했고 이후 노트에 적어가며 설계 시뮬레이션을 해봤다.

그리고 파이썬으로 코드를 구현했다.

코드를 구현하고도 실수했던 부분이 꽤 많아서 테스트케이스 100% 맞추는 데까지 총 4시간 걸렸다.

노트에 적은 과정은 다음과 같다. 

왼쪽부터 오른쪽으로 1,2,3,4

 

코드

N, M, K = map(int, input().split()) # 입력값 받기
maze = [list(map(int, input().split())) for _ in range(N)]  # 입력 받은 미로 정보, (0,0) 부터 시작한다.
moveCnt = 0 # 모든 참가자들의 이동거리 합
# 좌표는 (r+1, c+1) 해서 출력해야 한다.

for i in range(N):
    for j in range(N):
        maze[i][j] = -maze[i][j]    # 1~9이면, 벽인데 편의를 위해서 음수로 변경한다. => (-1 ~ -9)

for _ in range(M):
    r, c = map(int, input().split())    # 입력받은 참가자의 좌표
    maze[r-1][c-1] += 1  # 미로에 참가자 수를 업데이트 해준다. => 1 이상의 자연수는 해당칸에 나타나는 참가자의 수를 말한다.
    
# 출구 좌표는 -10으로 미로에 업데이트 해준다.
exit_r, exit_c = map(int, input().split())
maze[exit_r-1][exit_c-1] = -10


# 출구 좌표는 자주 필요하므로 함수로 구현한다.
def findExit():
    for i in range(N):
        for j in range(N):
            if maze[i][j] == -10:
                return (i, j)

# 참가자들이 이동하는 함수.
def moveAll():
    global moveCnt
    newMaze = [[0 for _ in range(N)] for _ in range(N)] # 이동한 결과를 저장할 배열
    nowExit = findExit()
    
    # 상하좌우 이동
    dx = [-1, 1, 0, 0]  # 상, 하, 좌, 우
    dy = [0, 0, -1, 1]
    
    # 미로를 확인하면서, 새로운 미로를 업데이트 해준다.
    for i in range(N):
        for j in range(N):
            if maze[i][j] >= -9 and maze[i][j] <= -1:   # 해당 격자가 벽이라면, 그대로 복사. 참가자가 없으니까~
                newMaze[i][j] = maze[i][j] 
                continue
            if maze[i][j] == 0: # 그냥 빈칸이라면, 
                continue
                
            # 참가자가 있다면, 상하좌우로 이동가능한지 체크한다. 짧아지는 방향으로 이동해야 한다.
            # 현재 좌표 : (i, j)
            curDist = abs(i-nowExit[0]) + abs(j-nowExit[1]) # 현재좌표에서 출구까지 거리.
            minDist = curDist   # 나중에 업데이트 될, 이동한 좌표에서 출구까지 거리. => minDist인 좌표로 이동가능하다.
            
            # 상하좌우 이동가능한지, 이동했을 때 출구까지 거리가 가까워지는지 확인한다.
            for d in range(4):
                nx = i + dx[d]
                ny = j + dy[d]
                if nx < 0 or nx >= N or ny < 0 or ny >= N:  # 이동한 좌표가 미로 범위를 넘어가면, 무시한다.
                    continue
                if maze[nx][ny] >= -9 and maze[nx][ny] <= -1:   # 이동한 좌표가 벽이라면, 무시한다.
                    continue
                # 이동가능 하다면, 출구까지 짧은거리와 해당 좌표를 업데이트 한다.
                afterDist = abs(nx-nowExit[0]) + abs(ny-nowExit[1])
                if minDist > afterDist: # 이동한 거리가 출구까지 거리와 더 가깝다면, 이동할 좌표를 갱신한다. (minI, minJ)를.
                    minDist = afterDist
                    minI = nx
                    minJ = ny
            
            # 상하좌우 이동불가능하다면, 그냥 그대로 있고 다음 격자 확인.
            if minDist == curDist:
                newMaze[i][j] += maze[i][j]
                continue
            
            # 이동가능 하다면,
            moveCnt += maze[i][j]   # 참가들이 움직이니까, 격자 안의 참가자 수 만큼 더해준다.
            
            # 탈출에 성공한다면,
            if maze[minI][minJ] == -10:
                continue
            
            # 그렇지 않다면, 나머지 애들도 탈출 시켜야지~
            newMaze[minI][minJ] += maze[i][j]
            
    
    # 이동이 완료된 미로를 새롭게 덮어쓴다.
    for i in range(N):
        for j in range(N):
            maze[i][j] = newMaze[i][j]

# subRotate : 찾은 정사각형을 90도 회전하고 감점 해준다.
def subRotate(x, y, d):
    a = [[0 for _ in range(d+1)] for _ in range(d+1)]   # maze 값 -> a로
    b = [[0 for _ in range(d+1)] for _ in range(d+1)]   # a의 회전된 값 -> b로
    
    # 오리지널 미로 값을 따로 가져온다.
    for i in range(d+1):
        for j in range(d+1):
            a[i][j] = maze[x+i][y+j]
    
    # a 배열을 90도 회전해서 b 배열에 저장하기.
    for i in range(d+1):
        for j in range(d+1):
            if a[i][j] >= -9 and a[i][j] <= -1: # 벽이라면, 내구도 변화한다.
                a[i][j] += 1
            b[j][d-i] = a[i][j]   # 90도 회전한다. (공식에 맞춰서 구할 수 있다.)
    
    # 다시 b배열을 미로에 복원한다.
    for i in range(x, x+d+1):
        for j in range(y, y+d+1):
            maze[i][j] = b[i-x][j-y]

# 이동 후에 정사각형을 회전해야 하므로 회전함수를 구현.
def Rotate():
    # 1. 정사각형의 크기를 결정한다. => 가장 작은 정사각형의 크기가 무엇일까?
    # 정사각형은 참가자와 출구를 포함해야 한다.
    
    minDist = 1000000   # 정사각형의 변의 길이.
    nowExit = findExit()    # 출구 좌표
    
    for i in range(N):
        for j in range(N):
            if maze[i][j] >= 1:  # 참가자가 있다면, 출구까지 거리를 재본다.
                dist = max(abs(i-nowExit[0]), abs(j-nowExit[1])) # 가로, 세로 중 큰 값이 가장 작은 정사각형이 된다.
                minDist = min(minDist, dist)    # 최소 정사각형을 찾는다. => 좌표의 차이기 때문에 칸 개념으로 하려면 +1 해줘야함.
    
    # 2. 작은 정사각형 크기 중, 좌상단의 숫자가 작은 것이 무엇일까? => 정사각형 위치 결정.
    bestRow, bestCol = -1, -1 # 좌상단.
    for i in range(N-minDist):
        for j in range(N-minDist):
            # 현재좌표 : (i, j)
            # 정사각형 우하단 좌표 : (i+minDist, j+minDist)
            
            # 좌상단이 (i, j) 인 정사각형의 격자를 살펴본다.
            # 출구와 사람이 둘 다 포함되어 있는 것을 확인하기 위해 체크 변수가 필요하다.
            flagExit, flagPerson = False, False     # 둘 다 True 이면 for문 탈출해도 된다.
            for r in range(i, i+minDist+1):
                for c in range(j, j+minDist+1):
                    if maze[r][c] == -10:   flagExit = True   # 출구가 포함되어 있다면, 
                    if maze[r][c] >= 1: flagPerson = True      # 사람이 포함되어 있다면,
            
            if (flagExit and flagPerson): # 좌상단이 (i, j)인 정사각형에 출구와 사람이 모두 포함되어 있다면, 바로 그것이 최소 정사각형 결정.
                bestRow = i
                bestCol = j
                break
        if bestRow != -1:
            break
    
    # 3. 찾은 최소 정사각형을 회전한다.
    subRotate(bestRow, bestCol, minDist)
            
    

# 게임종료 확인
def isFinish():
    for i in range(N):
        for j in range(N):
            if maze[i][j] > 0: # 참가자가 한명이라도 있으면, 아직 다 못빠져나간것(게임종료 불가능)
                return False
    return True


# Main은 이렇게 돌아간다.
for _ in range(K):
    # 1. 이동한다.
    moveAll()

    # 2. 참가자들이 탈출했는지 확인한다.
    if isFinish():
        break
    
    # 3. 미로를 회전한다.
    Rotate()
    

nowExit = findExit()
print(moveCnt)
print(nowExit[0]+1, nowExit[1]+1)

 

실수한 부분은?

디버깅을 하면서 찾아낸 실수이다. 생각보다 너무 많아서 좌절할 뻔했지만... 다음에는 이런 실수 안 해야지.

실수한 부분에 디버깅 Breakpoing를 찍어놨다.

1. 참가자가 있는 좌표는 1 이상의 자연수로 업데이트해줘야 하는데, 한 칸에 여러 명 있을 때 고려하지 않고 덮어쓰는 문제 발생.

 

2. moveCnt 변수 글로벌로 선언 안 해서 moveAll 함수에서 사용 못하는 문제 발생

 

3. 참가자가 이동했는데, 마침 그 자리가 출구라서 탈출이 가능하다면, 더 이상 탐색하지 않고 다른 격자를 봐야 하는데 continue를 빼 묵음.

 

4. 90도 회전할 때 공식을 잘못 구함. 🥲

 

5. 문제에서는 좌상단이 (1,1)이지만 내 코드에서는 (0,0)으로 구현했기 때문에, 최소 정사각형의 좌상단 좌표를 초기화할 때는 (-1,-1)로 설정해야 한다.