코드트리 메이즈러너 | python | 부분 회전

문제

링크

풀이

막혔던(헷갈렸던) 부분

1. 참가자가 이동할 수 있는 경우가 2개 이상일 때 어떻게 처리하지?

   • 처음 시도한 방식 : candidate라는 리스트를 선언해서 후보지를 모두 모으고, 우선순위에 따라 sort()하여 첫번째 값을 꺼내는 방식으로 구현함

   • 위 방식으로 해도 틀리진 않는 것 같음. 그러나 해당 문제는 경우의 수에 대한 우선순위 처리 로직이 꽤 단순한 편이므로 조건문 순서만 잘 지정해주어도 바로 풀림

   • 해당 부분 함수 move_all_traveler()

     # 모든 참가자를 이동시킵니다.
     def move_all_traveler():
       global exits, ans
     
       # m명의 모든 참가자들에 대해 이동을 진행합니다.
       for i in range(1, m + 1):
           # 이미 출구에 있는 경우 스킵합니다.
           if traveler[i] == exits:
               continue
           
           tx, ty = traveler[i]
           ex, ey = exits
     
           # 행이 다른 경우 행을 이동시켜봅니다.
           if tx != ex:
               nx, ny = tx, ty
     
               if ex > nx: 
                   nx += 1
               else:
                   nx -= 1
     
               # 벽이 없다면 행을 이동시킬 수 있습니다.
               # 이 경우 행을 이동시키고 바로 다음 참가자로 넘어갑니다.
               if not board[nx][ny]:
                   traveler[i] = (nx, ny)
                   ans += 1
                   continue
     
           # 열이 다른 경우 열을 이동시켜봅니다.
           if ty != ey:
               nx, ny = tx, ty
     
               if ey > ny: 
                   ny += 1
               else:
                   ny -= 1
     
               # 벽이 없다면 행을 이동시킬 수 있습니다.
               # 이 경우 열을 이동시킵니다.
               if not board[nx][ny]:
                   traveler[i] = (nx, ny)
                   ans += 1
                   continue

2. 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 어떻게 찾는가?

   • 핵심 기능인데 그냥 저 문장 자체를 정확히 이해 못했음
   • 왜 이해가 안되었는지 생각해보니까 참가자 관점 으로 (직사각형이 아닌) 정사각형을 어떻게 만들지를 꼬아서 고민해서 그런 것 같음
   • 생각이 꼬이면 그냥 더 단순하게 생각하자. 그게 정석 풀이 일 수 있음. 실제로 해당 문제는 정사각형 관점 으로 길이가 2인 정사각형부터 n-1정사각형까지 y,x좌표 움직이면서 완전탐색으로 하나씩 살펴보는 것이 답이었음

3. (2번 이어서) 가장 작은 정사각형이 여러 개 일때 어떻게 처리하지?

   • 이것도 1번과 동일하게 for문 돌릴 때 순서만 잘 고려하면 따로 candidate 리스트를 만들어서 후처리하고 할 필요가 없다
     • 가장 작은 정사각형 부터 (2~n)
     • 가장 작은 r좌표부터 (0,n~1)
     • 가장 작은 c좌표부터 (0,n~1)
   • 이렇게 탐색하면 조건에 부합하는 정사각형을 찾는 순간 return 해주면 됨

짚고 넘어가야 할 것

1. 좌표 인덱스 에러로 디버깅만 2시간 넘게 하다가 결국 정답 코드를 빌려왔다. 너무 꼬이면 그냥 함수 자체를 새롭게 다시 짜는게 정신건강에 좋을 듯 하다
2. 특히 부분 회전할 때 한 번에 규칙 생각해서 한 줄로 표현하려고 하지 말고 주석처럼 step별로 진행하자 꼭. 디버깅할 때 지옥을 맛보기 싫다면 꼬옥...

• rotate_90.py

  # 정사각형을 시계방향으로 90' 회전합니다.
  for x in range(sx, sx + square_size):
     for y in range(sy, sy + square_size):
         # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
         ox, oy = x - sx, y - sy
         # Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) . (y, square_n - x - 1)가 됩니다.
         rx, ry = oy, square_size - ox - 1
         # Step 3. 다시 (sx, sy)를 더해줍니다.
         next_board[rx + sx][ry + sy] = board[x][y]

3. 전역 변수 잘 활용할 것
4. 계속 좌표가 이동하는 사물(사람)은 전역에 1차원 리스트로 저장해두고 계속 업데이트 할 수 있도록 하기
5. 자잘한 처리들 빼놓지 않기
   • 참가자 모두 이미 탈출했는데 반복문을 돌리는 경우
   • 탈출구에 있는 참가자가 정사각형 내에 있다고 생각하고 코드를 짠 경우
     등등등

코드

아래는 코드트리 해설 코드입니다

n, m, k = tuple(map(int, input().split()))
# 모든 벽들의 상태를 기록해줍니다.
board = [
    [0] * (n + 1)
    for _ in range(n + 1)
]

for i in range(1, n + 1):
    board[i] = [0] + list(map(int, input().split()))

# 회전의 구현을 편하게 하기 위해 2차원 배열을 하나 더 정의해줍니다.
next_board = [
    [0] * (n + 1)
    for _ in range(n + 1)
]

# 참가자의 위치 정보를 기록해줍니다.
traveler = [(-1, -1)] + [
    tuple(map(int, input().split()))
    for _ in range(m)
]

# 출구의 위치 정보를 기록해줍니다.
exits = tuple(map(int, input().split()))

# 정답(모든 참가자들의 이동 거리 합)을 기록해줍니다.
ans = 0

# 회전해야 하는 최소 정사각형을 찾아 기록해줍니다.
sx, sy, square_size = 0, 0, 0


# 모든 참가자를 이동시킵니다.
def move_all_traveler():
    global exits, ans

    # m명의 모든 참가자들에 대해 이동을 진행합니다.
    for i in range(1, m + 1):
        # 이미 출구에 있는 경우 스킵합니다.
        if traveler[i] == exits:
            continue
        
        tx, ty = traveler[i]
        ex, ey = exits

        # 행이 다른 경우 행을 이동시켜봅니다.
        if tx != ex:
            nx, ny = tx, ty

            if ex > nx: 
                nx += 1
            else:
                nx -= 1

            # 벽이 없다면 행을 이동시킬 수 있습니다.
            # 이 경우 행을 이동시키고 바로 다음 참가자로 넘어갑니다.
            if not board[nx][ny]:
                traveler[i] = (nx, ny)
                ans += 1
                continue

        # 열이 다른 경우 열을 이동시켜봅니다.
        if ty != ey:
            nx, ny = tx, ty

            if ey > ny: 
                ny += 1
            else:
                ny -= 1

            # 벽이 없다면 행을 이동시킬 수 있습니다.
            # 이 경우 열을 이동시킵니다.
            if not board[nx][ny]:
                traveler[i] = (nx, ny)
                ans += 1
                continue


# 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 찾습니다.
def find_minimum_square():
    global exits, sx, sy, square_size
    ex, ey = exits

    # 가장 작은 정사각형부터 모든 정사각형을 만들어봅니다.
    for sz in range(2, n + 1):
        # 가장 좌상단 r 좌표가 작은 것부터 하나씩 만들어봅니다.
        for x1 in range(1, n - sz + 2):
            # 가장 좌상단 c 좌표가 작은 것부터 하나씩 만들어봅니다.
            for y1 in range(1, n - sz + 2):
                x2, y2 = x1 + sz - 1, y1 + sz - 1

                # 만약 출구가 해당 정사각형 안에 없다면 스킵합니다.
                if not (x1 <= ex and ex <= x2 and y1 <= ey and ey <= y2):
                    continue

                # 한 명 이상의 참가자가 해당 정사각형 안에 있는지 판단합니다.
                is_traveler_in = False
                for l in range(1, m + 1):
                    tx, ty = traveler[l]
                    if x1 <= tx and tx <= x2 and y1 <= ty and ty <= y2:
                        # 출구에 있는 참가자는 제외합니다.
                        if not (tx == ex and ty == ey):
                            is_traveler_in = True

                # 만약 한 명 이상의 참가자가 해당 정사각형 안에 있다면
                # sx, sy, square_size 정보를 갱신하고 종료합니다.
                if is_traveler_in:
                    sx = x1
                    sy = y1
                    square_size = sz

                    return


# 정사각형 내부의 벽을 회전시킵니다.
def rotate_square():
    # 우선 정사각형 안에 있는 벽들을 1 감소시킵니다.
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            if board[x][y]: 
                board[x][y] -= 1

    # 정사각형을 시계방향으로 90' 회전합니다.
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            ox, oy = x - sx, y - sy
            # Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) . (y, square_n - x - 1)가 됩니다.
            rx, ry = oy, square_size - ox - 1
            # Step 3. 다시 (sx, sy)를 더해줍니다.
            next_board[rx + sx][ry + sy] = board[x][y]

    # next_board 값을 현재 board에 옮겨줍니다.
    for x in range(sx, sx + square_size):
        for y in range(sy, sy + square_size):
            board[x][y] = next_board[x][y]


# 모든 참가자들 및 출구를 회전시킵니다.
def rotate_traveler_and_exit():
    global exits

    # m명의 참가자들을 모두 확인합니다.
    for i in range(1, m + 1):
        tx, ty = traveler[i]
        # 해당 참가자가 정사각형 안에 포함되어 있을 때에만 회전시킵니다.
        if sx <= tx and tx < sx + square_size and sy <= ty and ty < sy + square_size:
            # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            ox, oy = tx - sx, ty - sy
            # Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) . (y, square_n - x - 1)가 됩니다.
            rx, ry = oy, square_size - ox - 1
            # Step 3. 다시 (sx, sy)를 더해줍니다.
            traveler[i] = (rx + sx, ry + sy)

    # 출구에도 회전을 진행합니다.
    ex, ey = exits
    if sx <= ex and ex < sx + square_size and sy <= ey and ey < sy + square_size:
        # Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
        ox, oy = ex - sx, ey - sy
        # Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) . (y, square_n - x - 1)가 됩니다.
        rx, ry = oy, square_size - ox - 1
        # Step 3. 다시 (sx, sy)를 더해줍니다.
        exits = (rx + sx, ry + sy)


for _ in range(k):
    # 모든 참가자를 이동시킵니다.
    move_all_traveler()

    # 모든 사람이 출구로 탈출했는지 판단합니다.
    is_all_escaped = True
    for i in range(1, m + 1):
        if traveler[i] != exits:
            is_all_escaped = False

    # 만약 모든 사람이 출구로 탈출했으면 바로 종료합니다.
    if is_all_escaped: 
        break

    # 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 찾습니다.
    find_minimum_square()

    # 정사각형 내부의 벽을 회전시킵니다.
    rotate_square()
    # 모든 참가자들 및 출구를 회전시킵니다.
    rotate_traveler_and_exit()

print(ans)

ex, ey = exits
print(ex, ey)