[백준] 12851번 숨바꼭질 2 (Python, 파이썬)

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

24/02/07 현재 난이도: 골드 4

쓰이는 알고리즘 : bfs

내가 생각하는 난이도: 딱 골드4

남의 도움을 받았는가? X

 

느낀점:  N의 범위를 0<N<=10만으로 문제를 잘못 읽어 몇번 틀렸다. 구현이 어려운 문제도 아닌데 이러면 안된다 ㅠㅜ..

앞으로 문제를 웬만하면 처음부터 잘 읽고 잘 안풀린다면 문제를 정독해보자

 

서론을 말해보자면

 

사실 이문제는 두달전?쯤 내가 BFS 구현이 조금 미흡했을 때, 몇 번 틀리고 포기했었던 문제이다.

 

 백준 사이트를 뒤지던 중 내가 틀렸지만 고치지않은 이 문제를 발견했다

그래서 BFS 구현이 늘기도 했고 다시 한번 풀어보기로 했다.

 

이제 본론으로 들어가서 어떻게 풀었는지에 대해 이야기해보자

 

우선 나의 코드이다.

 

 

 

 

코드를 설명해보자면

 

먼저 N의 최댓값이 10만이므로

길이가 10만1인 리스트를 만들어준다

그리고 그 리스트(li) 안에 모든 값에 절대 답이될 수 없는 최댓값을 넣어준다

li는 임의의정수 k 가 있다고 할 때,

li[k] 는 k번째 칸에 갈 수 있는 최단 시간을 기록한다

나는 10의 11승을 집어넣었다

그후 덱의 자료구조를 가지는 q를 선언하고

이후에 현재위치인 N 과 움직인 횟수(즉 시간) 인 0 을 q에 넣는다

즉 q에 (N,0)을 넣는다

이후 내가 구하고 싶은 답(K에 최소 시간에 도착한 횟수)을 dap=0으로 일단 설정해준다

 

이후  while 문을 이용해서 q에서 원소를하나씩 빼고 넣어가며 bfs를 실행해준다

q에서 뽑은것을 현재 위치를 뜻하는 now와 시간을 뜻하는 t 로 나누어 준다

이후 만약에 li[now]가 t보다 크다면 now 칸에 도착 했을 때, 최단시간이 갱신 된것이므로

li[now]=t라고 해준다

그리고 만약 now 가 내가 원하는 K라면 dap=1 로 답을 초기화시킨다.(최단 시간을 갱신했으므로 횟수를 다시 1로 초기화 해줘야 한다.)

그리고 최단시간이 갱신 되었을 때 그게  내가 원하는 K가 아니라면, 

만약  now+1,now-1,now*2 가 0과 10만 사이에 있다면 q에 (now+1,t+1) 이나 (now-1,t+1) 이나 (now*2,t+1)을 넣어준다.

만약에 최솟값이 갱신되지는 않지만 li[now]가 t랑 같을 때, 만약에 now가 K이면 dap+=1 을 해준다

왜냐하면 최소시간에 도착하는 경우가 한가지 더 늘어난것이기 때문이다.

하지만 li[now] 와 t는 같지만, now가 K 가아닐 때는 q에 넣는 과정을 반복 해주면 된다

 

이렇게 하고나면 dap은 최솟값이 나온 횟수가 되고

li[K]는 최소시간이 나온다

 

따라서 위와 같은 코드가 된다.

 

마지막으로,,,

 

앞에 틀린 두 코드는

처음에는 최솟값을 갱신하지못하면 q에 넣어주지 않았었다.

 

즉 위에 코드에서 23번째줄 부터를 해주지 않았다

그렇게 하니 dap에 값이 제대로 설정되지 않았다.

 

다음 두번째 제출 때는

 

다 제대로 써줬으나... 0을 N에 포함을 안해줬다 ㅋ.ㅋ

 

확실히 BFS 구현하는 능력은 좀 늘었다!

앞으로 구현실력을 더 올려보자