[코드트리 🥇3] 메이즈 러너 (Python/파이썬)

1️⃣ 문제

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

​
올해 상반기 삼성 코테 기출문제이다
문제가 정말 삼성스럽다.. 시뮬시뮬
​
이차원 리스트 회전하는 코드를 못짜서 풀이를 참고해서 풀었다🥲

2️⃣ 풀이

1. 입력 받기

n, m, k = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

entry = []   # 참가자의 위치
for _ in range(m):
    y, x = map(int, input().split())
    entry.append([y-1, x-1])

exit = list(map(int, input().split()))  # 출구의 좌표 
exit[0] -= 1
exit[1] -= 1
answer = 0   # 참가자들의 이동거리 합 

이때 좌표가 1부터 시작하기 때문에 입력값에서 1씩 빼줘야 한다
처음에 출구의 좌표에서 1 빼는 걸 놓쳤다

2. 참가자 이동

• 1초마다 모든 참가자는 동시에 한 칸씩 상하좌우로 움직인다
• 이때, 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단거리(∣x1−x2∣+∣y1−y2∣)가 가까워야 한다
• 움직일 수 있는 칸이 2개 이상이라면, 상하로 움직이는 것을 우선시
• 움직일 수 없으면 움직이지 않음
• 한 칸에 2명 이상의 모험가가 있을 수 있음
• 참가자는 출구에 도달하면 즉시 탈출함

dy = [-1, 1, 0, 0]   # 상하좌우
dx = [0, 0, -1, 1]

visit = set()   # 정사각형 잡을 때 사용 
moved = []   # 이동한 참가자의 좌표 
for y, x in entry:
	dist1 = abs(y-exit[0]) + abs(x-exit[1])  # 현재 머물러 있는 칸의 출구까지 거리
	flag = False   # 움직임 여부 표시 

	for i in range(4):
		ny = y + dy[i]
		nx = x + dx[i]
        
        # 참가자는 벽이 없는 곳(빈칸 or 출구)으로 이동할 수 있다
        if 0 <= ny < n and 0 <= nx < n and board[ny][nx] == 0:
        	dist2 = abs(ny-exit[0]) + abs(nx-exit[1])  # 움직인 칸의 출구까지의 거리
			if dist2 < dist1:  
            	# 이동한 칸이 출구가 아니라면 리스트에 추가해줌 
				if not (ny == exit[0] and nx == exit[1]):
					moved.append([ny, nx])
					visit.add((ny, nx))
				flag = True
				break 
    
    # 움직일 수 없으면 움직이지 않음 
	if not flag:
		visit.add((y, x))
		moved.append([y, x])
        
    # 움직였다면 이동거리를 더해줌 
	else:
		answer += 1

상하로 움직이는 게 우선시되기 때문에, 상하로 먼저 이동을 고려해주었다

3. 미로 회전

• 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 잡음
• 가장 작은 크기를 갖는 정사각형이 2개 이상이라면, 좌상단 r 좌표가 작은 것이 우선되고, 그래도 같으면 c 좌표가 작은 것이 우선됨

​
출구의 좌표와 참가자의 위치를 전달받아, 정사각형의 좌표를 리턴하는 함수를 만들었다

def find(exit, visit):
    start, end = [0, 0], [0, 0]
    flag = False
	
    # 참가자와 출구를 모두 포함하려면 정사각형 길이는 2 이상일 것 
    for size in range(2, n):
        for sy in range(0, n-size+1):
            for sx in range(0, n-size+1):
                ey = sy + size - 1
                ex = sx + size - 1
				
                # 출구가 정사각형 내부에 포함되는지 확인
                if sy <= exit[0] <= ey and sx <= exit[1] <= ex:
                    # 참가자가 정사각형 내부에 포함되는지 확인
                    for y, x in visit:
                    	# 한 명이라도 포함되면 종료
                        if sy <= y <= ey and sx <= x <= ex:
                            start = [sy, sx]
                            end = [ey, ex]
                            flag = True
                            break
                if flag:
                    break
            if flag:
                break
        if flag:
            break
    
    return start[0], start[1], end[0], end[1]

좌표가 작은 것이 우선되는데, 0부터 확인하므로 조건에 만족한다

• 선택된 정사각형은 시계방향으로 90도 회전하며, 회전된 벽은 내구도가 1씩 깎임

​
내가 못 푼 부분이다..
이차원 리스트 90도 회전 코드는 알고 있었지만, 내가 알고 있는대로 쓰면 결과가 이상했다☹️
시작 좌표를 (0, 0)으로 이동시켜준 뒤 회전해야 했던 것!!!!

sy, sx, ey, ex = find(exit, visit)  # 가장 작은 정사각형의 좌표 
rotate = copy.deepcopy(board)
m = ey - sy + 1   # 정사각형의 길이 

# 정사각형 회전
for i in range(sy, ey+1):
	for j in range(sx, ex+1):
		oy, ox = i-sy, j-sx   # ⭐️(sy, sx) -> (0, 0)
		ry, rx = ox, m-oy-1
		if board[i][j] > 0:
			rotate[ry+sy][rx+sx] = board[i][j] - 1
		else:
			rotate[ry+sy][rx+sx] = board[i][j]

# 정사각형 내부에 있는 참가자 좌표 회전
for i in range(len(moved)):
	if sy <= moved[i][0] <= ey and sx <= moved[i][1] <= ex:
		oy, ox = moved[i][0]-sy, moved[i][1]-sx
		ry, rx = ox, m-oy-1
		moved[i] = [ry+sy, rx+sx]

# 출구 회전 
oy, ox = exit[0]-sy, exit[1]-sx
ry, rx = ox, m-oy-1
exit = [ry+sy, rx+sx]

​
그리고 또 실수했던 부분은
참가자 모두 출구로 이동해 탈출하면 바로 반복문을 종료시켜야 한다는 것이다
나는 참가자들이 탈출한 이후에도 미로를 회전시켜서 출구 좌표가 마이너스가 나왔었다
반복문 종료 시점을 생각없이 반복문 마지막에 넣지 좀 말자..

3️⃣ 코드

import copy

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

n, m, k = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

entry = []
for _ in range(m):
    y, x = map(int, input().split())
    entry.append([y-1, x-1])

exit = list(map(int, input().split()))  # 출구의 좌표 
exit[0] -= 1
exit[1] -= 1
answer = 0   # 참가자들의 이동거리 합 

def find(exit, visit):
    start, end = [0, 0], [0, 0]
    flag = False

    for size in range(2, n):
        for sy in range(0, n-size+1):
            for sx in range(0, n-size+1):
                ey = sy + size - 1
                ex = sx + size - 1

                if sy <= exit[0] <= ey and sx <= exit[1] <= ex:
                    for y, x in visit:
                        if sy <= y <= ey and sx <= x <= ex:
                            start = [sy, sx]
                            end = [ey, ex]
                            flag = True
                            break
                if flag:
                    break
            if flag:
                break
        if flag:
            break
    
    return start[0], start[1], end[0], end[1]


answer = 0
for t in range(k):
    # 참가자 이동 
    visit = set()
    moved = []
    for y, x in entry:
        dist1 = abs(y-exit[0]) + abs(x-exit[1])  # 현재 머물러 있는 칸의 출구까지 거리
        flag = False   # 움직임 여부 표시 
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
        
            # 참가자는 벽이 없는 곳(빈칸 or 출구)으로 이동할 수 있다
            if 0 <= ny < n and 0 <= nx < n and board[ny][nx] == 0:
                dist2 = abs(ny-exit[0]) + abs(nx-exit[1])  # 움직인 칸의 출구까지의 거리
                if dist2 < dist1:  
                    # 이동한 칸이 출구가 아니라면 리스트에 추가해줌 
                    if not (ny == exit[0] and nx == exit[1]):
                        moved.append([ny, nx])
                        visit.add((ny, nx))
                    flag = True
                    break 
        
        # 움직일 수 없으면 움직이지 않음 
        if not flag:
            visit.add((y, x))
            moved.append([y, x])
        # 움직였다면 이동거리를 더해줌 
        else:
            answer += 1
    
    # 미로를 탈출했을 경우 
    if len(moved) == 0:
        break

    # 미로 회전 
    sy, sx, ey, ex = find(exit, visit)
    rotate = copy.deepcopy(board)
    m = ey - sy + 1
    
    for i in range(sy, ey+1):
        for j in range(sx, ex+1):
            oy, ox = i-sy, j-sx
            ry, rx = ox, m-oy-1
            if board[i][j] > 0:
                rotate[ry+sy][rx+sx] = board[i][j] - 1
            else:
                rotate[ry+sy][rx+sx] = board[i][j]
    
    for i in range(len(moved)):
        if sy <= moved[i][0] <= ey and sx <= moved[i][1] <= ex:
            oy, ox = moved[i][0]-sy, moved[i][1]-sx
            ry, rx = ox, m-oy-1
            moved[i] = [ry+sy, rx+sx]

    oy, ox = exit[0]-sy, exit[1]-sx
    ry, rx = ox, m-oy-1
    exit = [ry+sy, rx+sx]

    board = copy.deepcopy(rotate)
    entry = copy.deepcopy(moved)

print(answer)
print(exit[0]+1, exit[1]+1)