[삼성 SW 역량 테스트 기출, Python] 메이즈러너 풀이

2023 상반기 오후 1번 문제인 '메이즈러너'의 Python 풀이입니다. 

 

1. 문제 링크

https://www.codetree.ai/ko/frequent-problems/problems/maze-runner/description

삼성 코딩테스트 기출 문제 설명: 메이즈 러너 | 코드트리

 

2. 한줄평

난이도 자체는 진짜 괜찮았는데 가장 작은 박스를 찾을 때 좀 깔쌈하게 해보려다가 엣지 케이스에 걸려서 1트에 틀린 문제..그냥 심플하게 구현하는게 젤 좋은것 같습니당😂

 

3. 풀이

N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
people_pos_list = []
total_move_distance = 0
for i in range(M):
    temp_x, temp_y = map(int, input().split())
    people_pos_list.append((temp_x-1, temp_y-1))

temp_goal_x, temp_goal_y =(map(int, input().split()))
goal_pos = (temp_goal_x-1, temp_goal_y-1)

def find_small_box():
    goal_pos_x, goal_pos_y = goal_pos

    for box_size in range(2, N+1):
        for x_start in range(0, N):
            for y_start in range(0, N):
                if x_start+box_size-1 < N and y_start+box_size-1 <N: # 범위 안에 만들어지는 사각형일 때
                    if x_start<=goal_pos_x<=x_start+box_size-1 and y_start<=goal_pos_y<=y_start+box_size-1:
                        is_in = False
                        for p_index in range(len(people_pos_list)):
                            p_x, p_y = people_pos_list[p_index]
                            if x_start<=p_x<=x_start+box_size-1 and y_start<=p_y<=y_start+box_size-1:
                                is_in = True
                                break

                        if is_in == True:
                            return (x_start, y_start), box_size


def rotate_board(start_pos, length):
    global board, goal_pos
    before_rotated_board = []
    after_rotated_board = []
    start_x, start_y = start_pos

    # board update

    for i in range(start_x, start_x+length):
        before_rotated_board.append(board[i][start_y:start_y+length])

    for row in zip(*before_rotated_board[::-1]):
        current_row = list(row)
        for idx in range(len(current_row)):
            if current_row[idx] > 0:
                current_row[idx] -=1
        after_rotated_board.append(current_row)


    current_row_idx = 0
    for i in range(start_x, start_x+length):
        board[i][start_y:start_y+length] = after_rotated_board[current_row_idx]
        current_row_idx +=1

    # people_position_update
    mid_x = (start_x + start_x+length-1)/2
    mid_y = (start_y + start_y+length-1)/2
    for p_index in range(len(people_pos_list)):
        temp_people_pos_x, temp_people_pos_y = people_pos_list[p_index]
        if start_x<=temp_people_pos_x<start_x+length and start_y<=temp_people_pos_y<start_y+length:
            diff_x = temp_people_pos_x-mid_x
            diff_y = temp_people_pos_y-mid_y
            new_people_pos = (int(round(mid_x + diff_y)), int(round(mid_y- diff_x)))
            people_pos_list[p_index] = new_people_pos

    # goal_position_update
    diff_goal_x = goal_pos[0]-mid_x
    diff_goal_y = goal_pos[1]-mid_y
    new_goal_pos = (int(round(mid_x + diff_goal_y)), int(round(mid_y- diff_goal_x)))


    goal_pos = new_goal_pos

def move_people():
    global people_pos_list
    current_move_distance = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for p_index in range(len(people_pos_list)):
        cur_people_x, cur_people_y = people_pos_list[p_index]
        cur_distance = abs(cur_people_x-goal_pos[0])+abs(cur_people_y-goal_pos[1])
        for dir in range(4):
            new_people_x, new_people_y = cur_people_x+dx[dir], cur_people_y+dy[dir]
            if 0<=new_people_x<N and 0<=new_people_y<N:
                if board[new_people_x][new_people_y] == 0:
                    new_distance = abs(new_people_x-goal_pos[0]) + abs(new_people_y-goal_pos[1])
                    if new_distance < cur_distance:
                        current_move_distance += 1
                        people_pos_list[p_index] = (new_people_x, new_people_y)
                        break
    return current_move_distance
def one_simulation():
    global total_move_distance, people_pos_list

    # step 1: 사람들 이동
    current_move = move_people()
    total_move_distance += current_move


    # 탈출한 애 있는지 검사
    new_people_pos_list = []
    for p_idx in range(len(people_pos_list)):
        if people_pos_list[p_idx] != goal_pos:
            new_people_pos_list.append(people_pos_list[p_idx])
    people_pos_list = new_people_pos_list

    # step2: 회전

    if len(people_pos_list) >0:
        start_pos, size = find_small_box()
        rotate_board(start_pos, size)


for step in range(K):
    if len(people_pos_list) >0:
        one_simulation()
    else:
        break
print(total_move_distance)
print_goal_pos = (goal_pos[0]+1, goal_pos[1]+1)
print(print_goal_pos[0], print_goal_pos[1])