티스토리 뷰
https://www.acmicpc.net/problem/14442
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
bfs를 이용해서 최단거리를 계산하는데, 벽을 뚫을 기회가 K번 있다.
따라서 큐에 현재 좌표, 깊이, 남은 벽을 뚫을수 있는 기회를 저장한다.
문제의 핵심은 중복 방문을 피하기 위해서 방문을 기록할 3차원 배열 mark[N][M][K] 를 만드는 것이다.
mark[2][2][1]은 (2,2)에 벽을 뚫을 기회가 1회 남았을때 도달할수 있는 최단 거리이다.
'PS' 카테고리의 다른 글
| 백준 1613. 역사 (0) | 2022.09.24 |
|---|---|
| 백준 14613. 너의 티어는? (0) | 2022.09.23 |
| 백준 1525. 퍼즐 (0) | 2022.09.20 |
| 백준 10159. 저울 (0) | 2022.09.20 |
| 백준 17085. 십자가 2개 놓기 (0) | 2022.09.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- permutation
- dfs
- graph
- priority queue
- 재귀
- Unity
- db
- floyd warshall
- Tree
- Stack
- 조합
- DP
- Spring
- Python
- 자료구조
- two pointer
- Implementation
- MVC
- greedy
- C++
- binary search
- back tracking
- Brute Force
- Kruskal
- BFS
- CSS
- C
- 이분탐색
- Dijkstra
- recursion
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |
글 보관함