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

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

프로그래머스

bfs 길찾기 문제인데

'도형의 테두리만 지나간다'라는 조건이 붙어

까다로운 문제.

초반에 접근법 생각이 잘 안나

질문게시판에서 힌트를 참고했습니다.

우선, 좌표의 스케일을 2배 늘리는 아이디어가 있습니다.

'테두리만 지나간다'했을 때

위의 도형과 같은 NG가 발생합니다.

그래서 스케일을 2배로 늘리고

returu값을 2로 나누면서

해당 NG를 해결할 수 있습니다.

질문게시판에 나온 힌트.

주어진 좌표대로 모두 점을 칠하고

'내부만 뚫어준다'

그럼 어떻게 내부를 구할까요?

point를 넣어준 점들을 하나하나식 보면서,

그림처럼 8가지 케이스가 모두 점이라면

내부의 점이라고 인식했습니다.

처음에는 상하좌우만 살폈지만,

그림에서처럼 상하좌우가 점인데도

테두리에 속한 점인 케이스가 존재했습니다.

어떻게 수정할까 고민하다가

8가지 케이스로 코드를 수정했습니다.

 

from collections import deque


def solution(rectangle, characterX, characterY, itemX, itemY):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    bd = [(0, -1), (0, 1), (1, -1), (1, 0), (1, 1), (-1, -1), (-1, 0), (-1, 1)]
    answer = 0
    x_min = 1e9
    x_max = 0
    y_min = 1e9
    y_max = 0

    for i in range(len(rectangle)):
        for j in range(4):
            rectangle[i][j] *= 2

    point = set()
    inside = deque()
    invi = set()

    for x1, y1, x2, y2 in rectangle:
        # 사각형 부분에 점들 다 찍어보기
        for x in range(x1, x2 + 1):
            for y in range(y1, y2 + 1):
                point.add((x, y))
        # 꼭지점 기준으로 상하좌우를 inside deque에 넣어줌
        # x,y값 최대 최소 범위
        x_min = min(x_min, x1)
        x_max = max(x_max, x2)
        y_min = min(y_min, y1)
        y_max = max(y_max, y2)

    cut = set()
    for x, y in point:
        bound = 0
        for d in range(8):
            nx = x + bd[d][0]
            ny = y + bd[d][1]

            if (nx, ny) in point:
                bound += 1

        if bound == 8:
            cut.add((x, y))

    point = point - cut

    q = deque()
    q.append((characterX * 2, characterY * 2, 0))
    visited = set()
    visited.add((characterX * 2, characterY * 2))

    while q:
        x, y, cnt = q.popleft()
        if x == itemX * 2 and y == itemY * 2:
            return cnt // 2
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < x_min or ny < y_min or nx > x_max or ny > y_max:
                continue
            if not (nx, ny) in point:
                continue
            if (nx, ny) in visited:
                continue

            visited.add((nx, ny))
            q.append((nx, ny, cnt + 1))