아이템 줍기

날짜 : 2023. 05. 30

사용 언어 : python

 

문제

 

코드

from collections import deque
def solution(rectangle, a, b, itemX, itemY):
    graph = [[-1] * 102 for _ in range(102)]
    for r in rectangle:
        x1, y1, x2, y2 = r
        x1 *= 2  # 2배처리
        y1 *= 2
        x2 *= 2
        y2 *= 2
        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                if x1 < i < x2 and y1 < j < y2:  # 테두리 채우기
                    graph[i][j] = -2  # 내부
                elif graph[i][j] != -2:  # 테두리
                    graph[i][j] = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    queue = deque()
    queue.append([a*2, b*2, 0])  # 현재위치 삽입
    while queue:
        x, y, cnt = queue.popleft()
        print(x, y, cnt)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx == itemX * 2 and ny == itemY * 2:  # 도착  
                return (cnt + 1) // 2
            if nx in range(102) and ny in range(102):  # 범위에 포함
                if graph[nx][ny] == 0:  # 방문하지 않았을 때
                    graph[nx][ny] = cnt + 1  # 방문처리
                    queue.append([nx, ny, cnt + 1])  # 삽입

 

 

풀이

- 기본적인 BFS로 설정해서 문제를 풀다보면 첫번째, 다섯번째 테스트케이스에서 오답이 발생한다.

- 꼭지점에서 1만큼씩 상하좌우로 이동하되, 테두리 라인에 맞추어 이동해야 하는데, 이를 건너뛰는 경우가 발생할 수 있기 때문이다.

 

- 예컨대 위 사진에서 빨간 점의 좌표는 (5, 5)이고, 각각 x축으로 1, y축으로 1 이동해도 테두리 라인이기 때문에 이동하는데는 문제가 없다.

- 그렇기에 원하는 패턴으로 이동시키기 위해 전체적으로 2를 곱함으로써 1씩 이동하여 발생할 수 있는 오류를 방지한다.

- 그 다음, 이중 for문을 사용하여 디폴트 값으로 -1로 채워진 그래프에서 테두리는 0, 내부는 -2로 채워나간다.

- 0은 이동거리를 체크하기 위한 용도로도 사용되기 때문에 해당 값으로 설정했다.

- 그 다음 현재 위치와 아이템 위치도 2배를 적용하여 BFS로 풀어내면 문제가 해결된다.

 

알게된 점

- 단순한 BFS문제라고 생각해서 범위를 51로 놓고 그냥 풀었다.

- 당연히 1, 5번째 테케에서 통과를 못했고, 머리를 싸맸다.

- 계속 고민한 결과 답이 안보였고, 다른 사람의 풀이를 참고했고 2배를 곱하는 아이디어를 깨달을 수 있었다.

- 그리고 아이디어를 찾아내니까 오류를 맞이했다.

- 에러는 TypeError: can only concatenate list (not "int") to list -> 연산 과정에서 서로 다른 타입끼리 이루어질 때 발생하는 오류였다. 

- 차근차근 코드를 뜯어보니 변수를 간략화한답시고 현재 위치를 r, c로 설정했는데 rectangle에서 for문을 돌릴 때 r, c로 설정해서 돌린 것이 문제였다.

- 그래서 이를 수정했고 문제없이 풀 수 있었다.

 

참고 사이트

- https://jyeonnyang2.tistory.com/247

[프로그래머스] 아이템 줍기 - 파이썬(python)