DP
-
BFS(너비우선탐색)는 있냐? 없냐? 만 기억하면 된다! (Python)Coding Test/Problem Solving 2022. 7. 18. 21:48
Problem BFS를 사용할 때에 가중치가 같다면 반드시 최솟값이 보장된다는 것이 이해가 안 갔다. 미로를 탐색한다고 했을 때 막다른 길이 있을 수도 있고 길이 여러 갈래로 나뉘어져있을 수도 있는데 이를 어떻게 확신할 수 있는 지 도무지 이해가 가지 않았다. Searching 백준에서 BFS 중 가장 기본 문제로 유명한 미로 탐색 의 이미지를 가져와봤다. 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 아래와 같은 미로에서 출발점으로부터 도착점까지의 최솟값을 구하는 문제다. 여기서 2가지만 기억하자. 인접한 좌표 중에서 벽이 아닌, 지나갈..