BFS
-
[BOJ] 13913 숨바꼭질 4PS/BOJ 2020. 7. 16. 18:26
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) BOJ 1697의 업그레이드 버전이다. https://moon323.tistory.com/16 이동하는 경로를 출력하는 부분이 추가되었다. 경로 추적은 이전에 BOJ 12852 1로 만들기2 https://moon323.tistory.com/6 에서 DP 경로 역추적을 하는 방식이랑 비슷하다. BFS에서 a->b로 ..
-
[BOJ] 13549 숨바꼭질 3PS/BOJ 2020. 7. 16. 18:20
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) BOJ 1697 숨바꼭질의 다른 버전이다. https://moon323.tistory.com/16 X*2 연산은 1초가 아닌 0초가 걸린다. -> 그냥 X*2 연산은 시간을 증가시키지 않으면 된다. 더보기 #include #include using namespace std; int N, K, h, c[100001];..
-
[BOJ] 12851 숨바꼭질 2PS/BOJ 2020. 7. 16. 18:15
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(V+E) BOJ 1697 숨바꼭질의 업그레이드 버전이다. https://moon323.tistory.com/16 N에서 K까지 이동하는데 걸리는 최단 시간뿐만 아니라 그 방법의 가짓수도 구해야한다. 접근: 1. 가짓수 구하기 -> 가짓수 구하는 문제이므로 Dynamic을 이용하면 된다. D[i]: i 좌표까지 가는 ..
-
[BOJ] 1697 숨바꼭질PS/BOJ 2020. 7. 16. 18:04
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) -> E K까지 최단 거리로 위치 이동 2. 한정된 이동 경로 (X-1, X+1, X*2) -> 이 두가지 조건을 통해 BFS를 사용하면 된다는 것을 알 수 있다. N~K까지 각 위치를 정점으로 보고 X-1, X+1, X*2 연산을 간선으로 생각하면 된다. 참고) 이동한 점이 10^5 보다 크면 고려할 필요가 없다. 이게 문제의..
-
[BOJ] 1520 내리막 길PS/BOJ 2020. 7. 16. 11:59
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(NM) 접근: 1. 지도가 주어지고 경로 탐색 2. 가능한(내리막길) 경로의 개수 구하기 -> 경로탐색은 보통 BFS로 접근하고, 가능한 가짓수를 구하는 문제는 보통 Dynamic으로 접근한다. D[i][j]: (i, j) 까지 가능한 경로의 가짓수 라고 하면, $$D[i][j] = \sum_{k=0}^N D[y_k][x_k]$$ $$(y_k,x_k):\..