[프로그래머스] 아이템줍기 (Python, Graph, BFS)

💡문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

문제는 아래와 같이 여러개의 사각형 정보(좌하단 좌표와 우상단 좌표)가 주어졌을 때 테두리를 따라 다각형 모양 지형이 만들어지고, 그 위에 캐릭터의 위치와 아이템의 위치가 주어졌을 때 아이템까지의 최단 거리를 구하는 문제입니다.

 

💡풀이

문제를 풀기 위해서는 두가지 과정이 필요합니다.

1. 테두리를 따라 게임 맵을 만들어야하고,
2. 그 테두리를 따라 최단거리를 구하면 됩니다.

저는 테두리를 따라서 최단거리를 구하는 것 전형적인 BFS 문제이기 때문에 간단하게 풀 수 있겠다고 생각했는데, 첫번째 과정, 즉 테두리를 만드는 것에서 고민을 많이 하였습니다. 그래서 이번 글에서는 제가 겪은 시행착오 과정을 그대로 작성해보려고 합니다.

첫번째로 제가 생각한 것은 문제에서 준 그대로 "구현"하는 것이었습니다. 우선 문제에서 가로 세로 최대가 50이라고 주었으니 -1로 채워진 2차원 리스트를 먼저 만들어놓고, 문제에서 주어진 사각형 정보를 순서대로 처리하면서
테두리는 1, 내부는 0으로 채웠습니다. 이때 사각형의 테두리가 다른 사각형의 내부와 겹치면 0(내부)로 처리하여 다각형을 만들 수 있도록 하였습니다. 이를 구현한 코드는 아래와 같습니다.

field = [[-1] * 51 for _ in range(51)]

for rectangle in rectangles:
    x1, y1, x2, y2 = rectangle

    for i in range(x1, x2 + 1):
        for j in range(y1, y2 + 1):
            if x1 < i < x2 and y1 < j < y2: # 사각형 내부
                field[i][j] = 0
            elif field[i][j] == 0: # 테두리인데, 이미 다른 사각형의 내부인 경우
                field[i][j] = 0
            else: # 테두리
                field[i][j] = 1

 

위의 코드를 실행하여 입출력예제 1번의 field를 print해보면 아래와 같습니다. (편의상 전체 맵의 크기를 20x20으로 줄였습니다.)

이렇게 뽑아놓고 보니 '오 문제에서 테두리를 그린것처럼 똑같이 나오니까 이제 BFS로 최단거리 구하면되겠다!' 하고 바로 BFS로 최단거리를 구해보았더니 아래와 같은 문제가 생겼습니다. 빨간색 부분이 문제가 되는 부분입니다.

형광색을 따라서 움직여야햐는데, BFS에서 상하좌우를 모두 탐색하다보니 테두리로 이어지지 않지만 인접해있는 부분으로 바로 넘어가서 최단거리가 잘못 계산되는 경우가 생기는 것이었습니다.

 

이를 해결할 수 있는 방법은 저 문제가 되는 부분을 떨어뜨려놓는 것입니다.

따라서 게임 맵 크기를 2배로 늘리고 사각형도 두배로 늘렸습니다. 그러면 아래처럼 문제가 되었던 부분이 떨어지게 되면서 정확하게 테두리만을 따라서 최단거리를 계산할 수 있습니다.

 

💡정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# programmers 아이템 줍기

from collections import deque


def solution(rectangles, characterX, characterY, itemX, itemY):
    answer = 0
    routes = []

    field = [[-1] * 102 for _ in range(20)]

    for rectangle in rectangles:
        x1, y1, x2, y2 = map(lambda x: x * 2, rectangle)

        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                if x1 < i < x2 and y1 < j < y2:
                    field[i][j] = 0
                elif field[i][j] == 0:
                    field[i][j] = 0
                else:
                    field[i][j] = 1

    character = (characterX * 2, characterY * 2)
    item = (itemX, itemY)
    visited = [[False] * 102 for _ in range(102)]
    queue = deque([character])
    visited[characterX * 2][characterY * 2] = True
    dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if field[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
                field[nx][ny] = field[x][y] + 1

    return field[itemX * 2][itemY * 2] // 2


rectangles = [[1, 1, 7, 4], [3, 2, 5, 5], [4, 3, 6, 9], [2, 6, 8, 8]]
characterX, characterY, itemX, itemY = 1, 3, 7, 8
print(solution(rectangles, characterX, characterY, itemX, itemY))

• 가로와 세로가 모두 최대 50이므로 field는 102x102로 생성합니다. (51 * 2)
• 문제에서 주어진 사각형의 정보(rectangle)를 모두 2배로 하여 field를 만듭니다.
• character의 위치도 마찬가지로 2배를 해줍니다.
• 방문했는지 확인하는 리스트(visited)와 queue를 만들어서 BFS 알고리즘을 구현합니다.
• field[itemX * 2][itemY * 2]에 저장된 최단거리를 2로 나누어 원래의 최단 거리를 리턴합니다.