profile
뉴비

백준 13913. 숨바꼭질 (Python)

문제 : https://www.acmicpc.net/problem/13913 풀이 bfs(너비우선탐색)을 통해 해결하는 문제이다. N에서 k까지 주어진 3가지의 이동방법(N-1,N+1,N*2)를 통해 최단거리로 이동하면서, 그 이동횟수와 이동방법을 출력해야한다. 처음엔 dp를 이용해 풀려했지만, 시간초과가 날 것 같아서 pass! 먼저 이미 왔던 길인지 확인하기 위한 li배열과, 해당위치로 오기전 이전위치를 알기위한 move배열을 만든다. 그리고 bfs를 통해 N부터 시작한다. 만약 현재위치(x)가 K일 경우, li[x]를 출력하고 리턴 x-1, x+1, x*2의 방법중 0<=i<=100000이고 해당위치를 방문하지 않았다면(li[i]==0) deque에 추가한 뒤, move[i]=x(i번째 위치를 오기전에는 x위치) N이 K까지 도달할 수 없는 방법은 없으므로 예외는 생략한다.(N+1만 반복해도 도달하므로) res배열에 K를 추가한 뒤, x=K로 선언 x가

2023년 2월 26일
·
0개의 댓글
·