728x90
코드만 궁금한 분은 깃허브링크
문제 설명은 스킵하겠습니다..!
문제 해결 논리
1. 스택에 [1, 0, 0] 넣은 후 1 -> 0 으로 표지(재방문 막기위해서). 이 때 [0, 0]은 시작점이고 1은 지금까지 지나온 노드의 갯수를 세기 위해서 저장한다.
2. 인접 요소 중 1로 표지돼있는 요소의 행/열값과 지금까지 지나온 노드의 수(이번의 경우에는 2)를 스택에 넣고 해당 요소를 1 -> 0으로 변경한다.
3. 스택을 힙으로 활용해, 지금까지 방문했던 수가 가장 작은 값을 스택에서 꺼내서 1~2번을 다시 반복한다.
가령 지금 [4,2,1]이라면, 0,0에서 2,1까지 오는데 총 4개의 요소 (예를 들자면 [0, 0], [1,0], [2,0], [2,1])를 지났다는 뜻이다.
이 문제를 우선순위 큐를 사용해 풀어야하는 이유는 목적지까지 가는 최소의 거리를 확인해야하기 때문이다. 우선순위 큐를 활용해야 어떤 임의의 노드까지 갈 때마다 가장 최소한의 거리를 이동하는 경우를 골라서 이동할 수 있다.
728x90
'코딩테스트 > 백준' 카테고리의 다른 글
| 백준 16953 A -> B 풀이/코드 (파이썬) 간단한 dfs문제! (0) | 2021.10.06 |
|---|---|
| 백준 1743번 음식물 피하기 풀이/코드 (파이썬) 기본 스택 문제 (0) | 2021.10.06 |
| 백준 1303번 전쟁 풀이/코드 (파이썬) 기본 스택 활용문제 (0) | 2021.10.06 |
| 백준 1260번 DFS와 BFS 풀이/코드 (파이썬) 자꾸 오류가 나는 경우 간단한 해결 방법 (0) | 2021.10.06 |
| 백준 2667번 단지번호붙이기 문제 해설/풀이/코드 (파이썬) 기본 스택 문제 (0) | 2021.10.05 |