설모의 기록

이 문제는 상, 하, 좌, 우로 1칸씩 이동하거나 말처럼 입력받은 K번만큼만 (상, 하) (좌, 우)로 두칸 또는 한칸씩 움직여 오른쪽 아래칸으로 이동하는데에 걸리는 시간을 구하는 문제입니다. 처음엔 DFS로 푸는게 더 간단할거라 생각해서 DFS로 풀다가 시간초과를 해결하지 못해 BFS로 방법을 바꿔 풀었습니다. 이번에는 계속 틀리길래 다른 분들의 코드를 검색해봤지만 로직이 뭐가 다른건지를 이해를 못했습니다T^T 2일동안 답답해하다 오류를 발견했는데, 저는 길을 찾지 못할 때 지금까지 걸린 시간을 출력해주고 있었습니다. -1을 반환해주는 코드로 바꾸니 맞았습니다. 너무 허탈하네요.. 기본 BFS에서 사용하는 dx, dy 배열을 12 길이의 배열로 바꾸고 for문에서 인덱스가 4보다 작을 때와 클 때를 나..

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다. BFS(Breath First Search) BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 장점너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.노드의 수가 적고 깊이가 얕은 해가 존재..