[BFS/DFS] 프로그래머스 level 3 아이템 줍기 (Python 파이썬)

💡문제 링크

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

프로그래머스

 

 

💡문제 분석 요약

직사각형 여러 개를 겹처서 경로를 만든다. 전체 직사각형의 테두리만 이동 가능하다.

정해진 출발점에서 끝점까지 이동하는 경로의 길이를 구하는 문제

 

💡알고리즘 설계

1. 경로 설정하기: 모든 직사각형의 테두리를 1로 설정한다. 그 후 모든 직사각형의 내부를 0으로 설정한다. 그러면  A직사각형의 테두리이지만 B직사각형의 내부인 경우 0으로 처리된다.

2. 최단거리로 이동하기: BFS 알고리즘을 사용한다. dx, dy 처리를 통해 상하좌우로 이동하고, 조건에 맞으면 그 위치로 이동한다.

 

💡코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    max_size = 102
    grid = [[0] * max_size for _ in range(max_size)]
    
    # 직사각형 테두리 처리
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for x in range(x1, x2+1):
            grid[x][y1] = 1
            grid[x][y2] = 1
        for y in range(y1, y2+1):
            grid[x1][y] = 1
            grid[x2][y] = 1
            
    # 직사각형 내부 처리
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for x in range(x1+1, x2):
            for y in range(y1+1, y2):
                grid[x][y] = 0
            
    # BFS 함수
    def bfs(start, end):
        # 초기 설정
        queue = deque([start])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        distance = 0
        visited = set()
        visited.add(start)
        # while문 반복
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                if (x, y) == end:
                    return distance // 2
                for dx, dy in directions:
                    nx ,ny = x + dx, y + dy
                    if 0 <= nx < max_size and 0 <= ny < max_size and (nx, ny) not in visited and grid[nx][ny] == 1:
                        visited.add((nx, ny))
                        queue.append((nx, ny))
            distance += 1
        return -1
    
    # BFS 함수 실행
    start = (characterX*2, characterY*2)
    end = (itemX*2, itemY*2)
    return bfs(start, end)

 

💡 느낀점 or 기억할정보

경로 처리

처음에 직사각형 경로 처리하는 것이 까다로웠다.

나는 직사각형 하나마다 1) 테두리를 +1하기 2) 내부를 -10으로 표시 3) 마지막에 음수인 부분은 0으로 바꾸기 로직을 떠올렸다.

그러나 다른 간단한 풀이가 있었다. 그냥 직사각형 하나마다 테두리를 1로 표시하기 - 를 끝낸 후, 그 다음에 직사각형 하나마다 내부를 0으로 표시하는 거다. 이러면 내부를 0으로 표시하면서 깔끔하게 내부가 처리된다.

또 다른 문제점을 마주했는데, 아래와 같은 상황의 경우 갈 수 있는 경우가 애매해진다는 것이다.

빨간점에서 파란점까지 이동하는 경우이고, 현재 초록점에 위치하고 있다고 하자. 아래로도 이동할 수 있고, 오른쪽으로도 이동할 수 있는 것처럼 보인다. 

하지만 실제로는 아래방향으로만 갈 수 있게 연결되어 있다. 그러나 이런 애매한 상황이 발생하기 때문에, 이를 해결하고자 전체적으로 크기를 2배로 늘렸다. 예를 들어 (1, 3)인 위치는 (2, 6)으로 바뀌는 것이다. grid의 크기도 50*50에서 101*101로 변경되었다.

이렇게 바꾸면 초록색 점에 위치했을 때 아래로 가는 경우의 수만 남게된다. 따라서 이렇게 경로를 구해주고, 마지막에 2로 나눠주기만 하면 된다.

전체적인 크기를 2배로 늘리는 건 아래와 같이 구현했다.

max_size = 102
    grid = [[0] * max_size for _ in range(max_size)]
    
    # 직사각형 테두리 처리
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for x in range(x1, x2+1):
            grid[x][y1] = 1
            grid[x][y2] = 1
        for y in range(y1, y2+1):
            grid[x1][y] = 1
            grid[x2][y] = 1
            
    # 직사각형 내부 처리
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for x in range(x1+1, x2):
            for y in range(y1+1, y2):
                grid[x][y] = 0

상하좌우 이동

이전에는  dx, dy를 아래와 같이 이용했다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(4):
  nx = x + dx
  ny = y + dy

그런데 더 간단한 방법도 있다는 걸 깨달았다.

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dx, dy in directions:
  nx ,ny = x + dx, y + dy

이 방법을 익혀둬야겠다.

BFS 방문처리

BFS를 이용할 때 방문처리를 위해 visited 배열이 필요하다. 이전에는 visited = [False] * (n+1) 방법을 많이 사용했는데, 이 문제에서는 visited를 집합 형식을 사용했다. 집합 형식을 사용할 때에는 visited = set()으로 빈 집합을 설정하고 visted.add(start)를 통해 시작점 정보를 넣어준다.

 

아 너무 어렵다..!