[프로그래머스] 아이템 줍기 (lv.3)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

---

풀이

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    MAX = 102   # 두배로 늘리기 때문에 최대 102

    # 테두리 그리기
    field = [[5]* MAX for _ in range(MAX)]  # 5는 맨 처음 땅
    for rec in rectangle:
        x1, y1, x2, y2 = map(lambda x:x*2, rec)
        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:  # 테두리 or 이미 내부가 아닐 때
                    field[i][j] = 1 # 테두리랑 내부랑 겹치면 그건 내부
    # 길찾기
    q = deque()
    q.append([characterX * 2, characterY * 2])
    visited = [[0] * MAX for _ in range(MAX)]
    visited[characterX * 2][characterY * 2] = 1

    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while q:
        x, y = q.popleft()

        if x == itemX * 2 and y == itemY*2:
            answer = (visited[x][y]-1) // 2
            break
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if visited[nx][ny] == 0 and field[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1

    return answer

---

설명

알고리즘도 이해되지 않았다ㅠㅠ

 

1. 테두리 그리기

- 2차원 배열을 만들고

- 테두리는 1, 내부는 0 으로 표시

- 테두리와 내부가 겹칠 경우 0으로 표시

- 2배를 주고 테두리를 잡았다: 2배를 하지 않으면 길이 아니더라도 1칸 차이가 날 수 있기 때문에 경로가 되어버린다.

 ※ 좌표가 인접한 경우 탐색을 제대로 하기 어렵다. 따라서, 좌표를 2배로 확대해서, 테두리 사이의 공간을 마련해 주어야 한다.