목록미로탐색 (1)

Devlog_by_0giru

[boj] 미로 탐색_2178

처음 이 문제를 봤을 때에는 dfs를 이용해 해결하려고 했으나, 최솟값을 구해주기 위해선 백트래킹 알고리즘을 생각해줘야 했는데 이 부분이 어려워 bfs를 이용해 해결했다. bfs는 큐를 이용해 문제를 해결하는데, 기초적인 이론으로 bfs를 설명하면 보통 그래프를 이용해 설명한다.(bfs알고리즘 포스팅 링크 첨부 예정) 이 문제는 x, y좌표를 이용한 이중 배열(리스트)를 이용하여 해결하는 문제였기 때문에 bfs 알고리즘을 실제로 코드에 녹여내기가 조금 어려웠다. 이런 문제처럼 x, y좌표를 통해 이중 배열(리스트)로 나타내는 모양을 이용하는 문제 유형이 대표적이니 반드시 익숙해져야 겠다고 느꼈다. 백준 예제 2번을 이용해 설명하겠다. 처음에 주어진 그래프가 있고 빈 큐를 선언했다. 처음 시작 부분의 좌표..
[PS] 2021. 3. 7. 01:52
이전 Prev 1 Next 다음