[백준] 13549번: 숨바꼭질3
0-1 BFS문제이다. 처음 생각했던 접근방식 처음에는 다이나믹 프로그래밍 방법을 생각했다.그 이유는 N과 K가 범위가 큰 상황에서 3가지 이동정보 (앞, 뒤, 2배 점프)를 고려하여최소 이동거리만 DP에 업데이트하면 될 것이라 생각했기 때문이다.그러나 일반적인 단방향 DP로 코드를 구성했을 때의 문제점은 N이 K보다 큰 상황일 때와 같은 양방향을 생각하기 복잡해지는 것이다. 그래서 보다 효율적인 풀이가 있을까 해서 다른 사람들의 풀이를 참고하였는데, 대부분 0-1 BFS라는 알고리즘을 사용하였다.BFS는 알고있지만 앞에 "0-1" 이 붙어있는 이유는 뭘까, 처음 접한 방법이라 호기심을 갖고 공부하였다. "0-1" BFS란 가중치가 0과 1로만 이루어져 있는 그래프에서 최단경로를 찾고자할 ..
2024.04.30