Level 3 아이템 줍기 Python 3

https://programmers.co.kr/learn/courses/30/lessons/87694?language=python3 

코딩테스트 연습 - 아이템 줍기

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_아이템줍기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque

def bfs(board, itemX, itemY, cx, cy, rectangle):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    q = deque([[cx, cy, 0]])
    visit = [[0] * 201 for _ in range(201)]
    visit[cy][cx] = 1

    while q:
        x, y, cnt = q.popleft()

        if x == itemX and y == itemY:
            return cnt

        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            if 0 <= nx <= 200 and 0 <= ny <= 200 and not visit[ny][nx] and board[ny][nx]:
                for sx, ey, ex, sy in rectangle:
                    if nx in range(sx, ex+1) and ny in range(sy, ey+1):
                        if nx in range(sx + 1, ex) and ny in range(sy + 1, ey):
                            break

                else:
                    visit[ny][nx] = 1
                    q.append([nx, ny, cnt + 1])


def solution(rectangle, characterX, characterY, itemX, itemY):
    board = [[0] * 201 for _ in range(201)]
    itemX *= 2
    itemY = (100 - itemY) * 2
    characterX *= 2
    characterY = (100 - characterY) * 2

    for i in range(len(rectangle)):
        rectangle[i][1] = 100 - rectangle[i][1]
        rectangle[i][3] = 100 - rectangle[i][3]
        for j in range(4):
            rectangle[i][j] *= 2
        for y in range(rectangle[i][3], rectangle[i][1] + 1):
            for x in range(rectangle[i][0], rectangle[i][2] + 1):
                board[y][x] = 1

    return bfs(board, itemX, itemY, characterX, characterY, rectangle)//2

---

풀이 과정

풀이 시간 1시간 16분

겹치는 사각형의 외곽으로만 캐릭터가 이동할 수 있는데 외곽인지 아닌지를 어떻게 판단해야 할지를 잘 생각해봐야 한다.

처음에 나는 사각형이 있는 부분을 1로 나타내주었다.

다음 이동할 상, 하, 좌, 우를 살펴보고 해당 위치가 어떤 사각형 범위에 포함되면서 내부에 위치하지 않다면 외곽임을 판단해주었다.

 

이때, 예제 1의 경우 예외상황이 발생한다.

(3, 5)에서 다음 위치를 (3, 6)과 (4, 6)으로 잡을 수 있다는 점이다.

(3, 6)은 사실상 사각형의 외곽이 아니지만 위에서 말한 조건에 부합하기 때문이다.

따라서, 이러한 예외를 제거하기 위해 전체 사각형의 길이와 아이템의 위치, 시작점의 위치를 2배로 늘려주어 해결할 수 있었다.

from collections import deque

def bfs(board, itemX, itemY, cx, cy, rectangle):
	#좌, 상, 우, 하
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    #[캐릭터의 위치, 이동 거리]를 큐에 담아준다
    q = deque([[cx, cy, 0]])
    
    visit = [[0] * 201 for _ in range(201)]
    
    #첫 시작위치 방문처리
    visit[cy][cx] = 1

    while q:
        x, y, cnt = q.popleft()
		
        #아이템 위치에 도착한 경우, 이동 거리를 return
        if x == itemX and y == itemY:
            return cnt
		
        #다음 이동할 위치 탐색
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            
            #board 내에 존재하면서 이전에 방문하지 않은 위치이면서 사각형이 존재하는 범위에 있는 위치인 경우,
            if 0 <= nx <= 200 and 0 <= ny <= 200 and not visit[ny][nx] and board[ny][nx]:
            	
                #해당 위치가 외곽에 존재하는지 탐색
                for sx, ey, ex, sy in rectangle:
                
                	#해당 위치가 어떤 사각형의 범위 내에 있는 경우,
                    if nx in range(sx, ex+1) and ny in range(sy, ey+1):
                    
                    	#해당 위치가 어떤 사각형의 내부에 있는 경우, 외곽이 아니므로 탐색을 종료한다
                        if nx in range(sx + 1, ex) and ny in range(sy + 1, ey):
                            break

				#외곽에 있는 위치인 경우, 방문처리 후 다음 탐색을 위해 큐에 담는다
                else:
                    visit[ny][nx] = 1
                    q.append([nx, ny, cnt + 1])


def solution(rectangle, characterX, characterY, itemX, itemY):
	#모든 입력값을 2배로 늘려주고 y좌표는 반전하여 기존 2차원 배열 표현과 일치시킨다
    board = [[0] * 201 for _ in range(201)]
    itemX *= 2
    itemY = (100 - itemY) * 2
    characterX *= 2
    characterY = (100 - characterY) * 2
    
    #사각형이 존재하는 영역을 board에 표시한다
    for i in range(len(rectangle)):
        rectangle[i][1] = 100 - rectangle[i][1]
        rectangle[i][3] = 100 - rectangle[i][3]
        for j in range(4):
            rectangle[i][j] *= 2
        for y in range(rectangle[i][3], rectangle[i][1] + 1):
            for x in range(rectangle[i][0], rectangle[i][2] + 1):
                board[y][x] = 1

    return bfs(board, itemX, itemY, characterX, characterY, rectangle)//2
    
#시간복잡도 = O(V+E), 공간복잡도 = O(n)