[BOJ] 백준 17836번 공주님을 구해라! c++

BOJ 문제 링크: https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

(n,m)크기의 성 입구 (1,1)에서 시작해 (n,m)위치에 있는 공주를 구하는 문제이다.

용사는 현재 무기로는 마법의 벽을 통과할 수 없으며, 성 어딘가에 반드시 한개 존재하는 '그람'을 얻으면 벽을 부수며 성내부를 이동할 수 있다.

 

기본적인 틀은 bfs를 사용한다. bfs를 이용하면 성에 각 칸을 최초로 발견할때마다 해당 칸을 최단시간에 발견한게 된다.

현재 상태에서 이동할 수 있는 다음칸들을 탐색할때 다음칸에 해당하는 cache가 비어있을 경우에만 queue에 push하고,

다음 칸들을 최초로 탐색할때마다 최초 탐색 시간을 cache에 저장한다.

만약 다음칸들을 탐색하다가 공주를 봤다면 현재시간 + 1 을 바로 return한다.

이때 cache는 '그람'을 소지했는지에 대한 상태도 나타낼수 있어야 하므로 3차원 배열로 표현한다.

 

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2317836.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!