[Programmers/프로그래머스] 코딩테스트 고득점 Kit DFS/BFS [코딩테스트 연습]

1. [Lv. 2] 타겟 넘버
2. [Lv. 3] 네트워크
3. [Lv. 2] 게임 맵 최단거리
4. [Lv. 3] 단어 변환
5. [Lv. 3] 아이템 줍기
6. [Lv. 3] 여행경로
7. [Lv. 3] 퍼즐 조각 채우기

📌 문제

---

📝 제한사항

---

💻 입출력 예

---

📖 입출력 예 설명

---

📌 풀이

---

from collections import deque

def BFS(startX, startY, endX, endY, graph):
    dx = [-1, 1, 0, 0]                              # 상하좌우순
    dy = [0, 0, -1, 1]                              # 상하좌우순
    visited = [[False] * 102 for _ in range(102)]   # 방문여부 2배 확장
    visited[startX][startY] = True                  # 시작지점 방문여부 True
    
    queue = deque([(startX, startY, 1)])            # (x, y, dist), dist 1부터 시작
    while queue:
        x, y, dist = queue.popleft()
        if x == endX and y == endY:                 # 아이템에 도달하면
            return dist                             # 이동거리 반환
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 102 and 0 <= ny < 102:                 # 그래프 범위 내
                if graph[nx][ny] == 1 and not visited[nx][ny]:  # 테두리이면서, 방문한 적이 없으면
                    visited[nx][ny] = True                      # 방문여부 True
                    queue.append((nx, ny, dist + 1))            # 다음위치, 이동거리 + 1
    return -1       # 목표지점에 도달할 수 없는 경우 -1 반환
    
    
def solution(rectangle, characterX, characterY, itemX, itemY):
    # ㄷ자 형태의 테두리의 경우, 평행한 두 테두리가 한 칸 차이일 때 방지
    graph = [[5] * 102 for _ in range(102)]         # 2배 확장
    for rect in rectangle:                          # 각 사각형의 좌표에 대해
        x1, y1, x2, y2 = map(lambda x: x * 2, rect) # 2배 확장
        for row in range(x1, x2 + 1):               # 현재 사각형의 Row 범위
            for col in range(y1, y2 + 1):           # 현재 사각형의 Col 범위
                if x1 < row < x2 and y1 < col < y2: # 현재 사각형의 내부인 경우
                    graph[row][col] = 0             # 0 
                elif graph[row][col] != 0:          # 현재 사각형의 테두리이면서, 다른 사각형의 내부가 아닌 경우
                    graph[row][col] = 1             # 1
    
    # 2배 확장하였으므로, 시작지점 및 아이템위치 2배 확장
    answer = BFS(characterX * 2, characterY * 2, itemX * 2, itemY * 2, graph)
    return answer // 2      # 2배 확장하였으므로, 2배 축소하여 정답 반환

핵심은 문제상황을 2배로 확장하여 해당문제를 해결한다는 사고를 할 수 있는지가 관건
'ㄷ자 형태의 테두리에서, 서로 평행한 두 테두리가 한 칸 차이인 경우'를 방지하기 위해
그래프 및 관련 변수를 2배 확장하여 문제를 해결한다.
ex) characterX, characterY, itemX, itemY, graph, answer 등 확장하거나 축소