[python] 프로그래머스 - 아이템 줍기(위클리 챌린지)

🤔문제 해결

• 테두리 그리기
  • 2차원 배열 만들어 두고
  • 테두리는 1, 내부는 0으로 표시
  • 테두리와 내부가 겹칠경우 0으로 표시

1번 예제 대충 크기 20잡고 테두리 만든 모습

• 위 그림이 예시의 방향과 다른 이유는 좌표계가 다르기 때문
• 그리고 2배를 주고 테두리를 잡았다
  • 그 이유는 2배를 안주면 길이 아니여도 1칸 차이가 날 수 있기 때문에 경로가 되어 버린다.

• 길 찾기는 BFS 로 최단거리 찾아주면 끝

 

💻소스 코드

from collections import deque


def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    MAX = 102  # 두배로 늘리기 때문에 최대 102
    # 테투리 그리기
    field = [[5] * MAX for _ in range(MAX)]  # 5는 맨처음 땅
    for rec in rectangle:
        x1, y1, x2, y2 = map(lambda x: x * 2, rec)
        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                if x1 < i < x2 and y1 < j < y2:  # 내부일 때
                    field[i][j] = 0
                elif field[i][j] != 0:  # 테두리일 때 그리고 이미 내부가 아닐 때
                    field[i][j] = 1  # 테투리랑 내부랑 겹치면 그건 내부

    # 길 찾기 (최단거리는 BFS)
    q = deque()
    q.append([characterX * 2, characterY * 2])
    visited = [[0] * MAX for _ in range(MAX)]
    visited[characterX * 2][characterY * 2] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        if x == itemX * 2 and y == itemY * 2:
            answer = (visited[x][y] - 1) // 2
            break
            
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if visited[nx][ny] == 0 and field[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1

    return answer

 

📕문제 확인

출처: 프로그래머스

링크: 아이템 줍기