최단 (1) 썸네일형 리스트형 [백준] 2178 미로탐색(JAVA) 풀이 학교 알고리즘 시간에 배웠던 미로탐색 문제인줄 알고 단순히DFS로 접근해서 모든경로의 이동수를 리스트에 저장하여 그중 가장 작은 수를 출력할려고 했다. 그러나 시간초과로 인해. 어떡게 풀어야 좋을지 몰랐다. 그래서 찾아보고 그러니 정답은 DFS가 아닌 "BFS"였다. 그러면서 다른 블로그에서는 최단, 최소를 찾을때는 BFS를 통해 구한다고 하여서 왜 그런지 몰랐다. 그러다 어느 블로그를 찾게 되었고 그 곳에 자세한 설명이 있었다. 간략하게 설명을 하면 BFS에선 간선(u,v)를 통해서, 정점 v를 처음발견해 큐를 넣었다고 가정한다. 이때, 시작점에서 v까지의 최단거리는 distanc[v]는 , 시작점에서 u까지의 최단거리 distance[u]에다가 1을 더한것이다. 조금더 풀어쓰자면 1. dista.. 이전 1 다음
