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

문제 링크

---

프로그래머스

 

접근

---

1. 주어진 직사각형 범위를 모두 1로 채운다.

2. 주어진 직사각형보다 1씩 작은 범위를 모두 0으로 채워 속을 비워낸다.

3. 테두리를 따라서 아이템에 도달할 때까지 BFS를 진행한다.

 

 

고민

---

만약 좌표 사이즈를 1로 하게되면, BFS시 명확하게 테두리를 구분할 수 없다.

아래 예시는 문제에서 주어진 예시 2번의 테두리를 매핑(위에서 언급한 접근 1번까지 수행)한 것이다.

접근 1 : 모든 속 채우기 진행

 

이제 테두리보다 1만큼 작은 위치의 테두리를 모두 비우면 다음과 같다. (접근 2를 통해 0으로 변경)

접근 2 : 테두리 안을 제거

 

 

이 상태에서 BFS를 수행할 수 있을까? 아래처럼 (7, 5) 위치에서 초록색 네모의 바깥 테두리가 아닌 안쪽 테두리로 인해 BFS가 안쪽도 테두리로 간주하고 돌게 된다. 

 

위의 케이스는 사실 문제가 없다. 어차피 (의도하지 못한) 안쪽 경로로 이동하더라도 (의도한) 바깥 경로가 시작에 도달하여 정확한 답을 도출해낸다. 문제는 다음 경우이다.

 

 

실제 사각형이 왼쪽처럼 위치했다고 가정하자. 이 테두리를 매핑해보면 오른쪽과 같다. 이 때 원래 의도대로라면 왼쪽 그림의 화살표처럼 BFS가 진행되어야 한다. 하지만 y축 1만큼의 차이(8 ~ 9)가 오른쪽 그림에는 반영되지 않는다. 

이 상태에서는 BFS가 오른쪽 그림의 화살표처럼 하나의 모서리로 간주가 되어버리며, 의도했던 답보다 더 적은 결과가 나오게 된다.

 

 

 

이를 해결하기 위한 방법은 단순하다. 기존 좌표 위치 * 2를 통해 2배만큼 크게 모든 것을 매핑하면 된다.

여기에서 모든 것이란 좌표, 시작점, 끝 점을 의미한다.

 

 

앞서 첫 번째 예시 결과를 2배 위치에 매핑하면 다음과 같다. 기존 (1, 1)의 점이 (2, 2)에 위치한 것에 유의하자.

이제 BFS를 하더라도 이전에 문제됐던 부분에서 안쪽 테두리를 탐색했던 문제는 사라진다.

왼 : 범위를 1로 채우기 / 오 : 내부를 0으로 채우기

 

그림으로 제시하지는 않았지만, 두 번째 예시에서 두 사각형이 1만큼의 차이로 인해 모서리가 드러나지 않았던 문제도 해결된다.

결론적으로 (이동한 거리 / 2) 만큼 하면 정답을 도출할 수 있다.

 

 

코드

---

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    board = [[0] * 102 for _ in range(102)]
    cX = characterX * 2
    cY = characterY * 2
    iX = itemX * 2
    iY = itemY * 2
    d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    visited = [[False] * 102 for _ in range(102)]

    # 내부 채우기
    for x1, y1, x2, y2 in rectangle:
        for i in range(y1 * 2, y2 * 2 + 1):
            for j in range(x1 * 2, x2 * 2 + 1):
                board[i][j] = 1

    # 내부 지우기
    for x1, y1, x2, y2 in rectangle:
        for i in range(y1 * 2 + 1, y2 * 2):
            for j in range(x1 * 2 + 1, x2 * 2):
                board[i][j] = 0

    # 캐릭터 위치 넣기
    visited[cY][cX] = True
    q = deque([(cX, cY)])
    while q:
        nX, nY = q.popleft()
        if nX == iX and nY == iY:
            return (board[nY][nX] - 1) // 2

        for i in range(4):
            pX = nX + d[i][0]
            pY = nY + d[i][1]

            if board[pY][pX] != 0 and not visited[pY][pX]:
                visited[pY][pX] = True
                board[pY][pX] = board[nY][nX] + 1
                q.append((pX, pY))

• return에서 결과 -1을 먼저 해준 이유는 최초 캐릭터의 위치에 1이 작성되어있었으며, 이를 더했었기 때문이다.