[Python] DFS/BFS : 프로그래머스 LV.3 아이템 줍기

문제 링크 :

프로그래머스

문제 해설 : 

사고의 흐름 :

• 음... 복잡해 보이네... 이건 그려봐야 알겠다...

• 문제를 풀기 위한 로직이 무엇이 있나 그림을 그려보면서 고민해 보았다. 
  1. 그래프에서 가장 큰 X값과 Y를 N,M 으로 두고 map의 크기를 세팅하고 전체 0으로 처리하는 로직.
  2. 사각형들의 테두리를 1로 바꾸는 로직.
  3. 사각형들 가장 바깥쪽 테두리 안쪽을 0으로 바꾸는 로직.
  4. 갈림길에서 경로를 이탈하는 것을 방지하기 위해 map의 크기를 두배로 확장시켜 주는( 갈림길 없애기) 로직.
  5. 방문한 노드들을 확인하면서 이동하는 로직.  

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
	answer = 0
    # 1이상 50이하의 map을 두배 확장맵으로 변경. 인덱스 0부터시작이라 102로 해줘야 2배.
    map = field = [[-1] * 102 for i in range(102)]

• 이 문제의 key point! 주어진 조건에서 갈림길이 생기기때문에 이것을 방지해 주기 위해서, 맵의 크기를 2배로 확장시켜 주기!

for r in rectangle:
        x1 = r[0] * 2
        y1 = r[1] * 2
        x2 = r[2] * 2
        y2 = r[3] * 2
        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

• 주어진 rectangle 정보를 이용하여, 사각형의 외곽을 1로 바꾸고 내부를 0으로 바꾼다.

전체 코드 :

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0 
    field = [[-1] * 102 for i in range(102)]
    for r in rectangle:
        x1 = r[0] * 2
        y1 = r[1] * 2
        x2 = r[2] * 2
        y2 = r[3] * 2
        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

    dx = [0, 0, -1, 1]  
    dy = [1, -1, 0, 0]  
    q = deque()
    q.append([characterX * 2, characterY * 2])   
    visited = [[1] * 102 for i in range(102)]  
    
    while q:    
        x, y = q.popleft()
        if x == itemX * 2 and y == itemY * 2:
            answer = visited[x][y] // 2
            break
        for k in range(4):
            nx = x + dx[k] 
            ny = y + dy[k] 
            if field[nx][ny] == 1 and visited[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1   
    return answer