BOJ 문제 링크 : https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
N * M 크기의 맵이 있다. 맵에서 벽은 1, 벽이 없는 곳은 0으로 표현된다.
(1,1)에서 (N,M) 위치까지 상하좌우로 한칸씩 이동면서 최단경로를 구하는 문제이다.
이때 벽을 부수고 이동하는 경우 경로가 더 짧아진다면, 벽을 한 개 까지 부수고 이동하여 된다.
bfs를 이용하면 문제를 해결할 수 있다. 이때 이미 지나온 곳을 다시 지나는것을 막기위해 discover배열을 둔다.
단, 벽을 부술 수 있는 상태인지 이미 벽을 부순 상태인지에 따라 이동할 수 있는 경로가 달라지므로 discover를 이차원이 아닌 3차원 배열로 한다.
코드원본: https://github.com/sbl133/BOJ/blob/main/%232206.cpp
GitHub - sbl133/BOJ
Contribute to sbl133/BOJ development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ] 백준 1987번 알파벳 c++ (0) | 2022.04.19 |
|---|---|
| [BOJ] 백준 1011번 Fly me to the Alpha Centauri c++ (0) | 2022.04.17 |
| [BOJ] 백준 7576번 토마토 c++ (0) | 2022.04.09 |
| [BOJ] 백준 1759번 암호 만들기 c++ (0) | 2022.02.15 |
| [BOJ] 백준 5430번 AC c++ (0) | 2022.02.11 |