[그래프]백준_2665_미로 만들기(Dijkastra)

• 알고리즘 유형 : Dijkastra, bfs, 그래프 탐색
• 풀이 참고 : 여러 블로그, 동기 설명
• 문제 링크 : https://www.acmicpc.net/problem/2665

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사드리겠습니다. 

---

Dijkastra 알고리즘 사용

이전 블로그에 정리하였음.

url : https://kyyu.tistory.com/29

 

---

풀이 요약

1. 최초 접근 -> 해결

  - 최소의 경우로 벽을 부수는 조건을 탐색하려 하였으나, 우리는 bfs를 다루고 있고 동기의 조언으로 벽을 다 부수는 방법을 생각했다.

2. 키포인트

  - bfs를 사용하면서 힙 큐를 할 때 카운팅 값을 같이 저장한다. 

  - 그리고 벽을 부술 때만 카운팅을 한다. 

 

---

코드(python)

import sys, heapq
# input = sys.stdin.readline

n = int(input())

arr = []
for i in range(n):
    arr.append(list(map(int, input())))

complete = [[0] * n for _ in range(n)] # 방문 체크

heap = [] # 힙큐 

def bfs(x, y):
    control_x = [-1, 1, 0, 0]
    control_y = [0, 0, -1, 1]
    heapq.heappush(heap, (0, x, y)) # 카운팅 정보를 같이 저장
    complete[x][y] = 1 # 방문체크
    while heap: # Dijkastra 시작
        count, r, c = heapq.heappop(heap)
        if r == n-1 and c == n-1:
            return count # 끝에 도달 했을때 카운팅 했던 값 리턴
        
        for i  in range(4):
            check_x = r + control_x[i]
            check_y = c + control_y[i]
            # 미로 끝으로 나가거나 뒤로가는 경우 제외
            if n > check_x >= 0 and n > check_y >= 0 and complete[check_x][check_y] == 0:
                if arr[check_x][check_y] == 1:
                    complete[check_x][check_y] = complete[x][y]
                    heapq.heappush(heap, (count, check_x,check_y))
                else:
                    heapq.heappush(heap, (count+1, check_x,check_y)) # 0에 닿으면 카운팅 1 하고 벽 부숨
                complete[check_x][check_y] = 1 # 위조건 다 방문 처리 해야함

print(bfs(0,0))

---

배운 점, 배울 점

1. 힙 큐에 넣으면서 카운팅을 같이할 방법을 다른 코드를 통해 발견했다. 이런 발상은 꼭 기억하자

2. 아직도 함수의 return 시점에 대해 더 공부해야 한다. 문제를 많이 풀자