[Python][구현] 메이즈 러너 - 코드트리 삼성 기출

[문제]

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

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

 

[알고리즘]

• 참가자 이동
  • exit의 y 좌표, 참가자의 y좌표 먼저 비교하여 위치 변경
  • 그 후, exit의 x 좌표, 참가자의 x좌표 먼저 비교하여 위치 변경
  • 이때, 조심해야할 것 before, after 데이터를 확실히 나누기. 변경된 값을 비교하는데 쓰일 수 있음
• 사람 존재하는지 여부 파악
  • 존재하지 않는다면 종료
• 미로 회전
  • 회전할 정사각형 영역 탐색
    • 2x2 크기부터 NxN 크기 정사각형마다, 좌상단부터 탐색(완탐)
    • 아래 코드 참고
  • 정사각형 회전
    • 아래 코드 참고

def set_square(exit):
    is_exit = False
    is_person = False
    for n in range(2,N+1):
        for i in range(N-n+1):
            for j in range(N-n+1):
                is_exit = False
                is_person = False
                for ii in range(n):
                    for jj in range(n):
                        if area_p[i+ii][j+jj] > 0:
                            is_person = True
                        elif area[i+ii][j+jj] == -1 :
                            is_exit = True

                if is_exit and is_person :
                    break
            if is_exit and is_person:
                break
        if is_exit and is_person:
            break
    return (i, j), (i+n-1, j+n-1)

def rotate_matrix(a):
    a_ = [[0 for _ in range(len(a))] for _ in range(len(a))]
    length = len(a)
    for i in range(length):
        for j in range(length):
            a_[j][length-1-i] = a[i][j]
    return a_

 

[느낀점 / 깨달은 점]

• 구현문제는 웬만하면 완탐으로 접근하자. (까다로운 예외처리가 필요한 나만의 알고리즘을 사용하지 말고)
  • 처음에 회전시킬 정사각형 탐색하는 함수를 구현할 때, exit 기준으로 bfs로 가까운 사람을 찾고, 가로 세로 중 긴 변을 찾아서.. 어찌구저찌구 로 구현하였는데, 너무 복잡하고, 디버깅할 때도 불편했다. 디버깅 포기하고 다른 사람 코드 보니 정사각형 크기 순으로 완탐으로 구현했더라. 다시 구현하니 훨씬 코드도 간략했음. (비록 for문이 5개지만..)
• 상태 변화가 있을 경우, before, after 상태를 각각 저장하자. 
  • 초반에 따로 저장을 안하고 구현하여서, 사람 옮길 때, 이전 사람이 이동한 후의 상태를 가지고 다음 사람 이동에 적용돼버림.. 
  • 꼭 before, after 따로 저장하자. 
• 그리고 벽, 사람 등 matrix 내 고려사항이 여러개라면, 서로 다른 Matrix로 저장하자.
  • 초반에 벽의 내구도가 담긴 배열, 사람의 인원수 배열을 같은 배열로 사용하였다. 벽의 내구도는 0~9, 사람의 인원은 10부터 시작. 1명이면 11, 2명이면 12.. 
  • 이렇게 되면 사람을 옮길 때 계산이 복잡해진다. 0부터 시작하는 각각 다른 배열을 사용하도록 하자.
• 처음 주어질 때부터 사람이 겹치게 주어진다는 것을 생각지 못했다. 다양한 경우의 수를 생각해야 한다. ㅎㅁㅇ. 
• 생각보다 회전 배열 구현이 간단하네?? 이건 빠르게 구현했다. 예전에 구현했을 때는 저 코드보다 길었는데.. 암튼 이건 만족.
• 내가 구현한 move_people() 코드는 너무 맘에 안들지만, 통과니까 뭐!

 

[코드]

import sys
from collections import deque

def print_2d(a):
    for i in a:
        for j in i:
            print(j, end=' ')
        print()
    print('=====')

def print_2d2(a, b):
    for i, j in zip(a, b):
        for ii, jj in zip(i, j):
            print(ii+ 10*jj, end=' ')
        print()
    print('=====')
    
def find_people_and_exit():
    exit = ()
    people = []
    for i in range(N):
        for j in range(N):
            if area_p[i][j] > 0 :
                people.append([i, j, area_p[i][j]])
            if area[i][j] == -1 :
                exit = (i, j)
    return people, exit

def move_people(people, exit):
    global final_move_length
    print('before final_move_length', final_move_length)
    ei, ej = exit
    p_after = people[:]

    for n, p in enumerate(people) :
        is_move = False
        is_skip = False
        pi, pj, n_p = p
        pii, pjj, _ = p
        if pi > ei :
            pii = pi -1
        elif pi < ei :
            pii = pi +1
        else :
            is_skip = True

        if not is_skip :
            # if not (pii < 0 or pjj < 0 or pii >=N or pjj >=N or 0 < area[pii][pjj] < 10) :
            if  pii >= 0 and pjj >= 0 and pii < N and pjj < N:

                if area[pii][pjj] == -1 : ## 출구일 때
                    p_after[n][0] = -1
                    p_after[n][1] = -1
                    final_move_length += n_p
                    continue
                elif area_p[pii][pjj] > 0: ## 사람이 있을 때
                    p_after[n][0] = pii
                    p_after[n][1] = pjj
                    # area[pii][pjj] += n_p
                    # area[pi][pj] = 0
                    final_move_length += n_p
                    continue
                elif area[pii][pjj] == 0 and area_p[pii][pjj] == 0: ## 아무도 없을 때
                    p_after[n][0] = pii
                    p_after[n][1] = pjj
                    # area[pii][pjj] = 10+n_p
                    # area[pi][pj] = 0
                    final_move_length += n_p

                    continue

        pii, pjj, _ = p

        if pj > ej :
            pjj = pj -1
        elif pj < ej :
            pjj = pj + 1
        else :
            continue

        if pii < 0 or pjj < 0 or pii >=N or pjj >=N or 0 < area[pii][pjj] < 10 :
            continue
        final_move_length += n_p
        if area[pii][pjj] == -1 : ## 출구일 때
            p_after[n][0] = -1
            p_after[n][1] = -1
            # area[pi][pj] = 0
        elif area_p[pii][pjj] > 0: ## 사람이 있을 때
            p_after[n][0] = pii
            p_after[n][1] = pjj
            # area[pii][pjj] += n_p
            # area[pi][pj] = 0
        elif area[pii][pjj] == 0 and area_p[pii][pjj] == 0: ## 아무도 없을 때
            p_after[n][0] = pii
            p_after[n][1] = pjj
            # area[pii][pjj] = 10+n_p
            # area[pi][pj] = 0
    area_p_after = [[0 for _ in range(N)] for _ in range(N)]
    for p in p_after:
        i, j, np = p
        if i == -1 and j == -1 :
            continue
        area_p_after[i][j] += np

    return area_p_after

def set_square(exit):
    is_exit = False
    is_person = False
    for n in range(2,N+1):
        for i in range(N-n+1):
            for j in range(N-n+1):
                is_exit = False
                is_person = False
                for ii in range(n):
                    for jj in range(n):
                        if area_p[i+ii][j+jj] > 0:
                            is_person = True
                        elif area[i+ii][j+jj] == -1 :
                            is_exit = True

                if is_exit and is_person :
                    break
            if is_exit and is_person:
                break
        if is_exit and is_person:
            break
    return (i, j), (i+n-1, j+n-1)

def rotate_matrix(a):
    a_ = [[0 for _ in range(len(a))] for _ in range(len(a))]
    length = len(a)
    for i in range(length):
        for j in range(length):
            a_[j][length-1-i] = a[i][j]
    return a_
    
def rotate_square(lu, rb):
    import copy
    lui, luj = lu
    rbi, rbj = rb
    temp_area = [a[luj:rbj+1] for a in area[lui:rbi+1]]
    temp_area_p = [a[luj:rbj+1] for a in area_p[lui:rbi+1]]

    temp_area = rotate_matrix(temp_area)
    temp_area_p = rotate_matrix(temp_area_p)

    for i in range(len(temp_area)) :
        for j in range(len(temp_area)) :
            if 0 < temp_area[i][j] < 10 :
                area[i+lui][j+luj] = temp_area[i][j] -1
            else :
                area[i+lui][j+luj] = temp_area[i][j]
            area_p[i + lui][j + luj] = temp_area_p[i][j]
    del temp_area

def rotate_miro(exit) :

    lu, rb = set_square(exit)
    rotate_square(lu, rb)


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

N, M , K = map(int, input().split())
area = [list(map(int, input().split())) for _ in range(N)]
area_p = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M) :
    i, j = map(int, input().split())
    area_p[i-1][j-1] += 1
exit = list(map(int, input().split()))


final_move_length = 0
area[exit[0]-1][exit[1]-1] = -1

for k in range(K):
    people, exit = find_people_and_exit()
    if len(people) == 0:
        break
    area_p = move_people(people, exit)
    people, exit = find_people_and_exit()
    if len(people) == 0:
        break

    rotate_miro(exit)

print(final_move_length)
_, exit = find_people_and_exit()
print(exit[0]+1, exit[1]+1)