[코드트리] 메이즈 러너 - Python

문제 링크

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20 

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

 

풀이 

어려웠던 점 

1. 최소 정사각형의 좌상단, 우상단 위치 구하기

2. 정사각형 시계 방향 회전 

 

graph : index에 해당하는 칸 별 내구도 저장 

players : player들의 위치 저장 

 

1. 참가자 이동 

def move(x,y):
	# 현재 위치에서 최단 거리 
    origin = abs(x-s_x) + abs(y-s_y)
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            continue 
    	
        # 이동했을 때 최단 거리 
        new = abs(nx-s_x) + abs(ny-s_y)
        # 최단 거리 줄어들고 
        if new < origin :
        	# 이동할 수 있는 칸이면 이동 
            if graph[nx][ny] == 0 :
                return nx,ny 
	
    # 이동할 수 있는 칸이 없는 경우
    return -1, -1

2. 최소 정사각형 찾기 

square = []
# 최소 정사각형 구하기 
for x,y in new_players :
    # 정사각형 크기 구하기 
    s_size = max(abs(x-s_x), abs(y-s_y))
    s_r, s_c = -1, -1

    # 좌상단, 우상단 위치 구하기 
    if abs(x-s_x) < abs(y-s_y) : 
        s_r = max(x,s_x) - abs(y-s_y)
        if s_r < 0 :
            s_r = 0 
        s_c = min(y, s_y)
    elif abs(x-s_x) == abs(y-s_y) :
        s_r = min(x,s_x)
        s_c = min(y,s_y)
    else :
        s_r = min(x,s_x)
        s_c = max(y, s_y) - abs(x-s_x)
        if s_c < 0 :
            s_c = 0 

    square.append((s_size+1, s_r, s_c))

# 크기 작은 순, r 작은 순, c 작은 순으로 정렬 
square.sort()

3. 정사각형 회전 & 출구 회전 & 내구도 -1 

회전할 때는 현재 위치에서 좌상단, 우상단 좌표를 빼준 위치에서 회전한다. 

그래야 0,0 좌표 기준으로 회전할 수 있게 됨 .

회전 시킨 후 다시 좌상단, 우상단 좌표 더하기 

def rotate(data):
    global s_x, s_y, n
    
    s = data[0]
    s_r = data[1]
    s_c = data[2]
    
    # 출구 회전 
    # 현재 위치에서 좌상단, 우상단 좌표를 빼줌 -> 0,0 기준으로 회전하게 됨 
    tmp_x = s_x - s_r 
    tmp_y = s_y - s_c 
    
    # 시계 방향 회전 
    tmp_x, tmp_y = tmp_y, s - tmp_x - 1 
    
    # 다시 좌상단, 우상단 좌표 더해줌 
    tmp_x += s_r 
    tmp_y += s_c
    
    # 출구 좌표 갱신 
    s_x = tmp_x
    s_y = tmp_y

    new_graph = [ [0] * s for _ in range(s)]
    
    for i in range(s_r, s_r + s):
        for j in range(s_c, s_c + s):
            # 마찬가지로 현재 위치에서 좌상단, 우상단 좌표 빼줌 -> 0,0 기준으로 회전 시키기 위함 
            x = i - s_r 
            y = j - s_c 
            # 회전 
            x, y = y, s - x - 1 
            
            # 0,0 기준으로 회전한 결과 new_graph에 대입 
            new_graph[x][y] = graph[i][j]

    for i in range(s):
        for j in range(s):
            graph[i+s_r][j+s_c] = new_graph[i][j]

    for i in range(s):
        for j in range(s):
            if graph[i+s_r][j+s_c] :
                # 내구도 1 씩 줄어듬 
                graph[i+s_r][j+s_c] -= 1

4. 정사각형 안에 포함된 플레이어들 회전

s, s_r, s_c = square[0]
rotate_players = []
# 정사각형 안에 포함된 플레이어들 위치 회전 
for x,y in new_players:
    if s_r <= x < s_r + s and s_c <= y < s_c + s :
        # 마찬가지로 0,0 좌표 기준으로 회전하기 위해 좌상단, 우상단 값 빼줌 
        nx = x - s_r 
        ny = y - s_c
        # 회전 
        nx, ny = ny, s-nx-1 
        # 다시 원래 위치로 
        nx += s_r
        ny += s_c
        rotate_players.append((nx,ny))
    # 정사각형 안에 포함되지 않은 경우 원래 위치 
    else :
        rotate_players.append((x,y))

# 플레이어 위치 갱신 
players = rotate_players

 

전체 코드 

from collections import deque 
import copy 

n, m, k = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

players = []

for _ in range(m):
    a,b = map(int,input().split())
    players.append((a-1,b-1))

s_x, s_y = map(int,input().split())
s_x -= 1 
s_y -= 1
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def move(x,y):
    # 현재 위치에서 최단 거리 
    origin = abs(x-s_x) + abs(y-s_y)
    
    # 상하 우선 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            continue 
    
        # 이동한 칸에서의 최단거리 
        new = abs(nx-s_x) + abs(ny-s_y)
        # 최단 거리 줄어듬 
        if new < origin :
            # 이동할 수 있는 칸 
            if graph[nx][ny] == 0 :
                return nx,ny 
    
    # 이동할 수 없는 경우 
    return -1, -1 

def rotate(data):
    global s_x, s_y, n
    
    s = data[0]
    s_r = data[1]
    s_c = data[2]
    
    # 출구 회전 
    # 현재 위치에서 좌상단, 우상단 좌표를 빼줌 -> 0,0 기준으로 회전하게 됨 
    tmp_x = s_x - s_r 
    tmp_y = s_y - s_c 
    
    # 시계 방향 회전 
    tmp_x, tmp_y = tmp_y, s - tmp_x - 1 
    
    # 다시 좌상단, 우상단 좌표 더해줌 
    tmp_x += s_r 
    tmp_y += s_c
    
    # 출구 좌표 갱신 
    s_x = tmp_x
    s_y = tmp_y

    new_graph = [ [0] * s for _ in range(s)]
    
    for i in range(s_r, s_r + s):
        for j in range(s_c, s_c + s):
            # 마찬가지로 현재 위치에서 좌상단, 우상단 좌표 빼줌 -> 0,0 기준으로 회전 시키기 위함 
            x = i - s_r 
            y = j - s_c 
            # 회전 
            x, y = y, s - x - 1 
            
            # 0,0 기준으로 회전한 결과 new_graph에 대입 
            new_graph[x][y] = graph[i][j]

    for i in range(s):
        for j in range(s):
            graph[i+s_r][j+s_c] = new_graph[i][j]

    for i in range(s):
        for j in range(s):
            if graph[i+s_r][j+s_c] :
                # 내구도 1 씩 줄어듬 
                graph[i+s_r][j+s_c] -= 1 
                
ans = 0 
for _ in range(k):
    new_players = []
    for x,y in players:
        nx, ny = move(x,y)
        # 이동할 수 없는 경우 이동하지 않음 
        if nx == -1 and ny == -1 :
            new_players.append((x,y))
        # 출구 도착 
        elif nx == s_x and ny == s_y :
            ans += 1
            continue
        # 이동 
        else :
            new_players.append((nx,ny))
            ans += 1 
    
    # 모든 플레이어 탈출 
    if len(new_players) == 0 :
        break 
    
    square = []
    # 최소 정사각형 구하기 
    for x,y in new_players :
        # 정사각형 크기 구하기 
        s_size = max(abs(x-s_x), abs(y-s_y))
        s_r, s_c = -1, -1
        
        # 좌상단, 우상단 위치 구하기 
        if abs(x-s_x) < abs(y-s_y) : 
            s_r = max(x,s_x) - abs(y-s_y)
            if s_r < 0 :
                s_r = 0 
            s_c = min(y, s_y)
        elif abs(x-s_x) == abs(y-s_y) :
            s_r = min(x,s_x)
            s_c = min(y,s_y)
        else :
            s_r = min(x,s_x)
            s_c = max(y, s_y) - abs(x-s_x)
            if s_c < 0 :
                s_c = 0 
        
        square.append((s_size+1, s_r, s_c))
    
    # 크기 작은 순, r 작은 순, c 작은 순으로 정렬 
    square.sort()
    # 회전 
    rotate(square[0])
    
    s, s_r, s_c = square[0]
    rotate_players = []
    # 정사각형 안에 포함된 플레이어들 위치 회전 
    for x,y in new_players:
        if s_r <= x < s_r + s and s_c <= y < s_c + s :
            # 마찬가지로 0,0 좌표 기준으로 회전하기 위해 좌상단, 우상단 값 빼줌 
            nx = x - s_r 
            ny = y - s_c
            # 회전 
            nx, ny = ny, s-nx-1 
            # 다시 원래 위치로 
            nx += s_r
            ny += s_c
            rotate_players.append((nx,ny))
        # 정사각형 안에 포함되지 않은 경우 원래 위치 
        else :
            rotate_players.append((x,y))
    
    # 플레이어 위치 갱신 
    players = rotate_players

print(ans)
print(s_x+1, s_y+1)