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

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

다각형 모양의 지형에서 아이템 찾으러 테두리만 둘아다녔을 때의 거리를 측정하는 문제이다.

코드

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0

    

    
    return answer

이렇게 한 칸 떨어진 지형을 디테일하게 확인하기 위해서 먼저 지도를 2배 확대시켰다.

    maps = [[0] * 200 for _ in range(200)]
    
    for r in rectangle:
      x1, y1, x2, y2 = r
      for y in range(2 * y1, (2 * y2)+1):
        for x in range(2 * x1, (2 * x2)+1):
          if maps[y][x] != 2 and (y == 2 * y1 or y == 2 * y2):
            maps[y][x] = 1
          elif maps[y][x] != 2 and (x == 2 * x1 or x == 2 * x2):
            maps[y][x] = 1
          else:
            maps[y][x] = 2

확대를 위해 가로 세로 200의 크기를 가진 maps라는 2차원 배열을 만들고, 각 직사각형의 점을 기준으로 테두리는 1로 내부는 2로 덮었다.
이 과정에서 어떤 직사각형에게는 테두리지만 다른 직사각형의 내부에 있는 점들은 2로 표시되었고, 아닌 부분은 1이 되었다.

그리고 BFS로 탐색을 시작했다.

    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    
    queue = [(characterY * 2, characterX * 2, 0)]
    idx = 0
    maps[characterY * 2][characterX * 2] = 0
    
    while idx < len(queue):
      y, x, t = queue[idx]
      idx += 1
      
      if y == 2 * itemY and x == 2 * itemX:
        answer = t // 2
        break
      
      for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        
        if 0 <= ny < len(maps) and 0 <= nx < len(maps) and maps[ny][nx] == 1:
          maps[ny][nx] = 0
          queue.append((ny, nx, t+1))

상하좌우 방향을 설정하고, que에는 시작좌표와 길이를 넣었다. 탐색을 하며 1인 점만 que에 추가하고 0으로 visited 처리를 해주었다.
탐색 중에 아이템을 만나면 정답에 2를 나눈 값을 answer에 저장하고 return했다.