그래프
-
[알고리즘] 백준 16930번 문제 (DFS, BFS)알고리즘 2021. 3. 28. 15:20
www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 문제를 읽어보면, 시작점에서 도착점으로 이동하는 최소 시간을 구하라고한다. 이 문제를 읽자 마자 '아하 이건 시작점, 도착점, 최소 시간이라는 키워드를 사용하는걸로 봤을때 너비 우선 탐색(BFS) 문제구나!' 하고 알 수 있어야한다. 이제 이건 알겠고, 그럼 이제 너비 우선 탐색으로 어떻게 코딩을 할 수 있을까를 생각해본다. 깊이 우선 탐색 (DFS) - 루트 노드(혹은 다른 임의의 노드)에서 시작해..