[Python][프로그래머스] 아이템 줍기 / BFS (Lv3)

🖇️ 링크 

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

프로그래머스

 

---

🙌 내 풀이 과정

---

🗒️ 파이썬 코드 풀이

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    
    # 좌표 생성 (110,110)
    SIZE = 110
    axis =  [[-1] * SIZE for _ in range(SIZE)]
    
    # 좌표 2배씩 확장
    for i in range(len(rectangle)):
        rectangle[i]  = list(map(lambda x : x*2 ,rectangle[i]))
        
    characterX, characterY, itemX, itemY = 2*characterX, 2*characterY, 2*itemX, 2*itemY 
    
    # rectangle 전부 1로 채우기
    for k in range(len(rectangle)):
        x1,y1,x2,y2 = rectangle[k]
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                axis[i][j] = 1
        
    # rectangle 테두리 제외하고 내부 0으로 채우기
    for k in range(len(rectangle)):
        x1,y1,x2,y2 = rectangle[k]
        for i in range(x1+1,x2):
            for j in range(y1+1,y2):
                axis[i][j] = 0
    
    # 동,남,서,북 방향으로 BFS 탐색
    dx,dy = [0,-1,0,1], [1,0,-1,0]
    q = deque([[characterX, characterY]])
    
    while q :
        x,y = q.popleft()
        if (x,y) == (itemX, itemY):
            # 초기 값 1 빼주기 & 이후 2배 축소
            answer = (axis[x][y]-1) // 2
            return answer
        
        # BFS 탐색 
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 1 < nx < SIZE and 1 < ny < SIZE :
                if axis[nx][ny] == 1:
                    axis[nx][ny] = axis[x][y] + 1  
                    q.append([nx,ny])
                    
    return answer

 

1. 풀이가 좀 복잡하 차근 차근 풀이를 해보자.

 

2. 이 문제의 핵심은 모든 좌표를 2배씩 확장하는 것이다.

• 우선 좌표 표현은 위와 같이 한다. 
  • (1,1)에는 직사각형의 테두리니까 1로 표현
• 하지만 이렇게 좌표를 표현했을 때, (3,5) 좌표 부분처럼 BFS 탐색에 문제가 생긴다.
• 이러한 이유 때문에 스케일을 2배로 확장해준다.
  • 2배 확장해도 거리 구하는데 지장은 없음

 

3. 첫번째로 직사각형의 테두리를 1로 채워주고 이후 내부를 0으로 채워준다.

• 간단하게 2중 for문을 2번 써서 가능

4. 이렇게까지 하면 이제 BFS로 탐색하면 된다.

• 위,아래,왼쪽,오른쪽 탐색을 위한 dx,dy 선언
• 초기값 Queue에 삽입
• 이후 방문하지 않은 좌표 방문하며 axis 값 갱신
• 목적지에 도달하는 경우 조건문으로 탈출 후 길이 축소

 

⏰ 시간 복잡도 

•  axis 좌표 1 또는 0으로 채우기
  • 직사격형 개수 R, 좌표 개수 100 
  • O ( R * (100)^2 )
• BFS 탐색 
  • V는 정점, E는 간선
  • O( V + E) 
  • 약 O ( 10,000 + 40,000)

→  시간 복잡도는 O(V+E), BFS 알고리즘 사용해도 시간 초과 문제 없음

 

---

📌  문제 코멘트 

이 문제가 LV3 ...??  아마 잘 못 측정된 것 같다 ...

BFS 구현 자체가 어렵지는 않는데, BFS 전까지 과정이 어렵다.

 

이 문제를 포스팅 하는 이유는 다음과 같다.

• 좌표를 어떤 관점에서 바라 볼 것인지 (보통은 2번처럼 봄)

• 스케일 2배 확장해서 문제 풀이
• 직사각현 테두리와 내부 구분하는 for문 

---

📚  문제