[프로그래머스] Lv3 아이템 줍기 Python

예전에 풀었을때도 막혔었던 문제이다...

다시 풀어도 풀이 방법이 떠오르지 않아 풀이를 보고 풀었던 문제이다.

 

이 문제의 핵심은 아래와 같은 상황(1번)에서 어떻게 모서리만 탐색할수 있는가라고 생각한다.

 

기존 방법은 사각형이 있는 곳만 1로 채운뒤

다음에 탐색할 점을 4방탐색으로 탐색한후 8방탐색으로 0(사각형이 없는 부분)이 있는 부분이 있으면 모서리라 판단하고 탐색할 점으로 정했다. 그러다 보다 1번과 같은 상황이 발생하였다.

 

생각해도 방법이 생각나지 않아 힌트를 보고 풀이를 떠올렸다.

 

풀이는 사각형, 시작점, 목표점의 값에 2를 곱한뒤 거리를 구하고 최종적으로 구한 길이를 2로 나누어 최단경로의 길이를 구하였다. (다음점을 구하는 로직은 기존의 방법과 같다.)

 

 

from collections import deque


def solution(rectangle, start_x, start_y, target_x, target_y):
    # 테두리 판단
    def is_border(tx, ty):
        for d in range(8):
            ntx = tx + dtx[d]
            nty = ty + dty[d]
            if graph[ntx][nty] == 0:
                return True
        # 8방 탐색 했을때 모든 점이 사각형 내부 점이라면 모서리가 아니다.
        return False

    # 배율
    zoom = 2
    for index, value in enumerate(rectangle):
        for i in range(4):
            value[i] = value[i] * zoom
        rectangle[index] = value
    start_x = start_x * zoom
    start_y = start_y * zoom
    target_x = target_x * zoom
    target_y = target_y * zoom
    answer = 0

    # 다음점 탐색
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # 모서리 탐색
    dtx = [1, 0, -1, 0, 1, 1, -1, -1]
    dty = [0, 1, 0, -1, -1, 1, 1, -1]

    # 사각형 그리기
    size = 51 * zoom
    graph = [[0] * size for _ in range(size)]
    for lx, ly, rx, ry in rectangle:
        for x in range(lx, rx + 1):
            for y in range(ly, ry + 1):
                graph[x][y] = 1

    # BFS
    queue = deque()
    queue.append([start_x, start_y, 0])
    visited = [[False] * size for _ in range(size)]
    visited[start_x][start_y] = True
    while queue:
        x, y, count = queue.popleft()
        if x == target_x and y == target_y:
            answer = count
            break
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 방문하지 않고 모서리의 후보인경우
            if not visited[nx][ny] and graph[nx][ny] == 1:
                # 모서리인 경우
                if is_border(nx, ny):
                    queue.append([nx, ny, count + 1])
                    visited[nx][ny] = True
    return answer // zoom