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

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

프로그래머스

 

• 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동

• 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현
• 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동

 

• 만약 직사각형을 겹친 후 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됨

 

• 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없음
• 아래 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없음

 

 

• 지형이 2개 이상으로 분리된 경우도 없음

 

 

• 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없음

 

 

 

• rectangle: 지형을 나타내는 직사각형이 담긴 2차원 배열
• characterX, characterY: 초기 캐릭터의 위치
• itemX, itemY: 아이템의 위치
• 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태
  • 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수
  • 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없음
  • 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어짐
• charcterX, charcterY는 1 이상 50 이하인 자연수
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어짐
• itemX, itemY는 1 이상 50 이하인 자연수
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어짐
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없음

 

"""
입출력 예시)

rectangle = [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]], characterX = 1, characterY = 3, itemX = 7, itemY = 8 -> 17
rectangle = [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]], characterX = 9, characterY = 7, itemX = 6, itemY = 1 -> 11
rectangle = [[1,1,5,7]], characterX = 1, characterY = 1, itemX = 4, itemY = 7 -> 9
rectangle = [[2,1,7,5],[6,4,10,10]], characterX = 3, characterY = 1, itemX = 7, itemY = 10 -> 15
rectangle = [[2,2,5,5],[1,3,6,4],[3,1,4,6]], characterX = 1, characterY = 4, itemX = 6, itemY = 3 -> 10
"""

 

 

## 의사코드 ##

# 가장 짧은 거리 -> BFS
# deque

# 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로

# BFS 수행

 

 

 

통과한 코드

 

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    # 모든 좌표값의 최댓값인 50의 2배 크기인 2차원 배열  
    field = [[-1] * 102 for _ in range(102)]
    
    # 직사각형 그리기
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, r) # 좌표를 그리기 위해 2를 곱함 
        # x1부터 x2까지
        for i in range(x1, x2+1):
            # y1부터 y2까지
            for j in range(y1, y2+1):
                # 테두리인 x1, x2, y1, y2 값을 제외한 내부만 0으로 채우기
                if x1 < i < x2 and y1 < j < y2:
                    field[i][j] = 0
                # 다른 직사각형의 내부가 아니면서 테두리일 때 1로 채우기
                elif field[i][j] != 0:
                    field[i][j] = 1
    # 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # BFS 수행
    q = deque()
    # 초기 캐릭터 위치에 2를 곱한 값을 큐에 삽입
    q.append([characterX * 2, characterY * 2])
    visited = [[1] * 102 for _ in range(102)] # 최단거리 기록

    while q:
        x, y = q.popleft()
        # 현재 위치가 아이템의 위치인 경우 최단거리를 2로 나눈 값 return 
        if x == itemX*2 and y == itemY*2:
            answer = visited[x][y] // 2
            break 
        # 상하좌우 이동
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 현재 위치가 테두리이면서 아직 방문하지 않은 위치라면 (visited의 초기 값: 1)
            if field[nx][ny] == 1 and visited[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1 # 최단거리 갱신
    return answer

 

• field를 모든 좌표의 최댓값인 (50+1)의 2배로 만드는 이유
  • 테두리가 인접해있는 경우 그 값이 중복될 수 있기 때문
  • -> 좌표를 그릴 때도 2를 곱해서 그리고, 최단거리를 구한 후 다시 2로 나눠줌

 

• [[-1] * n] 과 [[-1] * n for _ in range(n)]의 차이

# [[-1] * n]
# : -1이 n개 있는 리스트가 하나만 들어있는 2차원 리스트
a = [[-1]* 3]
print('a:', a)
print('len(a):', len(a)) # -> 전체 2차원 리스트의 길이 = 1
print('len(a[0]):', len(a[0]), '\n') # -> 한 리스트의 길이 = n

# [[-1] * n for _ in range(n)]
# -1이 n개 있는 리스트가 n개 들어있는 2차원 리스트 
b = [[-1]* 3 for _ in range(3)]
print('b:', b)
print('len(b):', len(b)) # -> 전체 2차원 리스트의 길이 = n
print('len(b[0]):', len(b[0])) # -> 한 리스트의 길이 = n

"""
a: [[-1, -1, -1]]
len(a): 1
len(a[0]): 3 

b: [[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
len(b): 3
len(b[0]): 3
"""

 

 

 

참고)

 

https://velog.io/@rlaalswn3282/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8%B0

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