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

프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS)

• Lv 3. 아이템 줍기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/87694#

Code

from collections import deque

def check_range(x, y, max_length):
    if (x < 0 or y < 0 or x >= (max_length * 2) + 1 or y >= (max_length * 2) + 1):
        return False
    return True

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

    # 가장 큰 크기의 좌표값 구하기 (만들 map의 크기 설정을 위해)
    max_idx = 0
    for i in range(len(rectangle)):
        for j in range(len(rectangle[i])):
            if (rectangle[i][j] >= max_idx):
                max_idx = rectangle[i][j]

    matrix = [list(0 for _ in range((max_idx * 2) + 1)) for _ in range((max_idx * 2) + 1)]

    # map 만들기
    for i in range(len(rectangle)):
        # 함수 그래프의 (x,y) 좌표는 2차원배열 인덱스에서 반대로 적용됨 (그래서 x -> y, y -> x로 표현)
        y1, x1, y2, x2 = rectangle[i][0], rectangle[i][1], rectangle[i][2], rectangle[i][3]
        # 좌표 2배로 확장
        x1, y1, x2, y2 = x1 * 2, y1 * 2, x2 * 2, y2 * 2     

        for x in range(x1, x2 + 1):
            for y in range(y1, y2 + 1):
                if(x1 < x < x2 and y1 < y < y2):    # 사각형의 내부인 경우 == 2로 채우기
                    matrix[x][y] = 2
                if(matrix[x][y] != 2):      # 테두리인 경우 == 1로 표시
                    matrix[x][y] = 1
	
		## BFS 탐색
    visited = [list(0 for _ in range((max_idx * 2) + 1)) for _ in range((max_idx * 2) + 1)]

    q = deque()

    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
		
		# 얘네도 좌표 2배 해주고, (x,y) 반대로 넣어주기
    item = [itemY * 2, itemX * 2]
    character = [characterY * 2, characterX * 2]

    q.append([character[0], character[1], 0])
    visited[character[0]][character[1]] = 1

    while (q):
        curr = q.popleft()
        y = curr[0]
        x = curr[1]
        cnt = curr[2]

        if (y == item[0] and x == item[1]):
            answer = cnt // 2
            break

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (check_range(nx, ny, max_idx) and visited[ny][nx] == 0 and matrix[ny][nx] == 1):
                q.append([ny, nx, cnt + 1])
                visited[ny][nx] = cnt + 1

    return answer

풀이 및 해설

• 생각한 방법 :
  • map을 표시할 때 좌표 크기를 다 2배씩 확장해서 꺾인 부분 제대로 그려놓고 → BFS 탐색 → 최종 답 리턴할땐 2로 나눠서 리턴
• 내가 그린 지도 모양
  (x → y, y → x 로 함수 좌표를 2차원 배열 인덱스랑 바꿔서 생각)
• 2배 전에 그려지는 지도
• 2배 하고 그려지는 지도
  
• 2배 그려진 지도에서 BFS 탐색 후 → visited 출력
• 테케 3개 계속 틀렸던 이유 : 맨 처음 while문에 들어가기 전에 큐에 캐릭터 위치 넣고 그 캐릭터의 visited 지정하는걸 인덱스를 잘못 지정했음…
• cnt를 큐에서 가지고 다니면서 이동 가능한 곳은 현재 cnt에서 한칸 이동한거니까 cnt+1로 다음 위치에 넣어주기
• 전체 지도만 제대로 그리면 바로 풀리는 문제인데 그게 너무 까다로웠다,,
• 예외 해결 테케 모음

  print(solution([[2, 1, 3, 6], [4, 1, 5, 6], [1, 2, 6, 3], [1, 4, 6, 5]], 3, 2, 5, 4))   # 8
  print(solution([[1, 1, 4, 4], [2, 2, 5, 5], [3, 3, 7, 8]], 1, 1, 5, 3))     # 6
  print(solution([[1, 1, 3, 7], [2, 2, 7, 4], [4, 3, 6, 6]] , 1 , 2, 6, 6 ))     # 13