[프로그래머스] 카카오 앱 정리하기

문제

코딩테스트 연습 - 카카오 앱 정리하기

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• N x M 크기의 격자가 주어집니다.
  • 각 칸에는 0은 빈칸을 의미하고, 숫자는 앱 ID를 의미합니다.
• 앱 특징은 다음과 같습니다.
  • 같은 ID는 정사각형 블록으로 주어집니다.
  • 크기는 다양합니다. (1x1 ~ kxk)
• 이때 앱 하나를 선택하여 상하좌우 중 한 방향으로 한 칸 밀 수 있습니다.
  • 이동하려는 위치에 다른 앱이 있으면, 그 앱도 같은 방향으로 한 칸 이동됩니다.
• 앱이 격자 밖으로 이동한 경우 반대편으로 이동합니다.
  • 반대편으로 이동한 위치에 앱이 있으면 마찬가지로 밀립니다.
• 크기가 2x2 이상인 앱은 한 칸이라도 밖으로 나가면 전체가 반대편으로 이동합니다.

입력 조건

• N, M : 2 ~ 10
• 앱 ID : 0 ~ 100
• commands 길이 : 1 ~ 1,000
  • commands[i] = [ID, arrow]
  • arrow = 1(오른쪽), 2(아래쪽), 3(외쪽), 4(위쪽)

출력

모든 명령을 수행 후에 격자의 상태를 반환.

---

문제 풀이

이 문제는 “반대로 이동” 때문에 생각보다 까다로운 문제이었습니다. 이 문제의 핵심은 다음과 같습니다.

앱 상태 관리

격자 전체를 직접 갱신하면서 관리하려고 하면, 이동마다 여러 칸을 업데이트해야 해서 로직이 복잡해집니다.

따라서 각 앱을 다음과 같은 형태로 관리하는 것이 훨씬 효율적입니다.

  app = [좌하단 x, 좌하단 y, 한 변의 길이]

이 방식의 장점은 다음과 같습니다.

• 이동: 좌표만 바꾸면 됩니다. O(1)
• 충돌 판정: 두 정사각형의 범위 비교로 해결할 수 있습니다.

단순 이동

이동 명령을 받은 앱(이동 주체)은 항상 한 칸 이동합니다. 이동하려는 위치에 다른 앱이 존재하면 해당 앱도 같은 방향으로 한 칸 이동합니다. 이러한 충돌 처리는 연쇄적으로 발생할 수 있습니다. 따라서 앱을 차례대로 밀어내는 방식은 재귀적으로 처리할 수 있습니다.

반대로 이동

반대로 이동은 다음과 같이 단순 이동으로 변환하여 처리할 수 있습니다.

그림과 같이 1번인 앱을 오른쪽으로 이동한 경우, 격자 왼쪽으로 이동하고 단순 이동을 한 변의 길이만큼 반복하여 단순 이동을 수행하면 됩니다.

즉, 반대로 이동은 “위치를 재배치한 후, 여러 번의 단순 이동을 수행하는 과정”으로 해석할 수 있습니다.

주의할 점

• 반대로 이동한 경우 밀려 나온 순서대로 처리해야 합니다.
  • 순서를 잘 못 처리하면 전체 상태가 달라집니다.
• 앱의 겪자 안/밖 여부를 판정할 때 두 가지 경우를 구분해야 합니다.
  • 격자 내부 -> 외부로 이동하는 경우, 겪자 밖으로 이동된 것이므로 반대로 이동을 수행 해야합니다.
  • 격자 외부 -> 내부로 이동하는 경우, 실제로는 겪자 밖에 있지만 이동 결과가 격자 내부이므로 내부에 있는 상태로 봐야 합니다.

---

풀이 코드

from collections import deque

# 1: 오른, 2: 아래, 3: 왼, 4: 위
dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def solution(board, commands):
    H, W = len(board), len(board[0])

    # app_pos[key] = [좌하단 x 좌표, 좌하단 y 좌표, app 크기 - 1]
    # key = app id
    app_pos = parse_app(board, H, W)

    for cmd in commands:
        # 격자 밖으로 밀려 이동 예정인 앱들 모음.
        to_move = deque()

        # 앱 이동.
        move_app(app_pos, cmd, H, W, 1, to_move)

        while to_move:
            now = to_move[0]
            now_app = app_pos[now]

            # 밖으로 이동.
            if cmd[1] == 1:
                now_app[0] = -1 - now_app[2]
            elif cmd[1] == 2:
                now_app[1] = -1 - now_app[2]
            elif cmd[1] == 3:
                now_app[0] = W
            else:
                now_app[1] = H

            # 한 변의 크기 만큼 이동. (격자 밖에서 안으로 이동)
            move_app(app_pos, [now, cmd[1]], H, W, app_pos[now][2] + 1, to_move)

            # 이동 후 삭제.
            to_move.popleft()


    answer = [[0] * W for _ in range(H)]

    # 앱을 격자에 넣기
    for key in app_pos:
        app = app_pos[key]

        for y in range(app[1], app[1] + app[2] + 1):
            for x in range(app[0], app[0] + app[2] + 1):
                answer[y][x] = key

    return answer


# 앱을 cnt 만큼 cmd에 따라서 이동 시킴.
def move_app(app_pos, cmd, H, W, cnt, to_move):
    app_id, arrow = cmd
    app = app_pos[app_id]

    for i in range(cnt):
        # 한 칸 이동.
        app[0] += dirs[arrow - 1][0]
        app[1] += dirs[arrow - 1][1]

        # 자체가 앱 밖으로 이동 -> 더 이상 다른 것을 맵 밖으로 이동 시키지 않음.
        # 따라서 남은 cnt 만큼 이동은 무의미.

        # cnt != 1 의미 : 격자 밖에서 안으로 이동 중임을 의미
        # 따라서 이동 주체가 앱 밖으로 이동 여부는 cnt == 1 인 경우에 만 직접 밖으로 이동
        if cnt == 1 and is_overflow(app, H, W):
            to_move.append(app_id) # 이동 예정에 추가.
            break
        else:
            # 다른 앱과 겹침 여부 확인.
            for key in app_pos:
                # 이동 주체 또는 이미 밖으로 이동 되어서 이동 에정인 것은 패스
                if key == app_id or key in to_move:
                    continue

                if is_over_lapping(app, app_pos[key]):
                    # 충돌 발생한 경우 재귀적으로 처리.
                    move_app(app_pos, [key, arrow], H, W, 1, to_move)


# board[][] -> app_pos {app_id: [sx, sy, size]}
def parse_app(board, H, W):
    res = {}

    for y in range(H):
        for x in range(W):
            if board[y][x] == 0 or board[y][x] in res:
                continue

            app_size = 1

            while y + app_size < H and board[y + app_size][x] == board[y][x]:
                app_size += 1

            res[board[y][x]] = [x, y, app_size - 1]
    return res


# 두 앱의 겹침 여부
def is_over_lapping(s1, s2):
    # s1 (x1, y1), (x2, y2)
    # s2 (x3, y3), (x4, y4)
    x1, y1 = s1[0], s1[1]
    x2, y2 = s1[0] + s1[2], s1[1] + s1[2]
    x3, y3 = s2[0], s2[1]
    x4, y4 = s2[0] + s2[2], s2[1] + s2[2]

    # 겹침 조건 : not (x2 < x3 or x1 > x4 or y2 < y3 or y1 > y4)
    return not (x2 < x3 or x1 > x4 or y2 < y3 or y1 > y4)


# 앱이 밖으로 나갔는지 판단
def is_overflow(app, height, width):
    if app[0] < 0 or app[0] + app[2] >= width:
        return True

    if app[1] < 0 or app[1] + app[2] >= height:
        return True

    return False