백준 12851 숨바꼭질 2 문제 풀이/해설/코드 (파이썬) 생각보다 간단한 큐, bfs 문제

코드만 궁금한 분은 깃허브링크

GitHub - Rhyankwon/algorithms

 

문제 설명은 스킵! 개인적으론 문제 이해는 쉬운데 풀기는 조금 까다로웠달까..

 

문제 해결 논리

 

1. 큐에 0, 시작값 넣기. 0을 넣는 이유는 연산의 수를 기록해야하기때문.

2. 큐에서 시작값을 빼고 거기에  -1, +1, *2 한 값을 다시 큐에 넣는다. 이 때 1을 같이 넣어준다.(연산 횟수 = 0 + 1 = 1)

3. 2번을 반복하는데 이 때 힙을 사용해서 연산횟수가 작은 순서대로 꺼낸다.(우선순위 큐)

4. 이렇게 하면n번의 횟수만에 시작값에서 우리가 원하는 값을 얻을 수 있게 되는데 연산횟수가 작은 순서대로 확인했으므로 그때의 연산횟수 값이 우리가 리턴해야 하는 값 중 하나이다.

5. 큐에 들어있는 값들 중 해당 연산횟수와 같은 값들을 모두 꺼내서 확인하면서 혹시 답을 만족하는 추가 경우의 수가 있으면 갯수를 카운트한다.

6. 이미 필요한 최소 연산횟수값이 나온 경우 큐에서 꺼낸 연산횟수값이 그것보다 크면 프로그램을 종료하고 답을 출력한다.

 

 

2-1. 이때 이미 방문한 값인지 확인해야 불필요한 연산을 줄일 수 있다.

3-1. 이 때 해당 값이 우리가 원하는 값 (0~100000)안에 있는지 매번 확인하면서 넣어야 불필요한 연산을 하지 않는다.

3-2. 우선순위 큐를 굳이 사용하는 이유는 연산횟수가 작은 순서로 값을 꺼내기 위해서인데 사실 우선순위큐를 사용하지 않고 그냥 덱을 사용해도 어차피 연산횟수가 작은 순서대로 값을 꺼내게 돼서 덱을 사용해도 된다. 실제로 같은 코드로 힙만 덱으로 바꿔서 풀었는데(풀이 2) 시간을 15%가량 줄일 수 있었다.

 

 

이 문제를 푸는게 약간 헷갈렸던 이유는, 사실 만약 N+1, N*2만 조건에 있었으면 dfs로도 풀 수 있었기 때문이다. 이 문제는 N-1이 포함돼서 자칫하면 루프에 걸려서 같은 값을 더하기 빼기만 계속 하는 경우가 생길 수가 있어서, 그리고 양방향이라서 자칫하면 답을 찾는 반대방향으로 계속 함수가 실행될 수가 있어서 dfs로는 풀 수 없다. 아무튼 그런 이유로.. 처음에 좀 헷갈렸었다. 우선순위큐/bfs를 잘 활용하면 풀 수 있는 문제이다. 우선순위큐가 아니라 덱을 사용해도 되지만 계속 우선순위큐를 언급하는 이유는 '최소 연산횟수'를 찾아야하고 그게 약간 비용문제..같은 느낌이 들어서, 그런 느낌을 못 받으면 위와같은 풀이를 생각할 수 있을까? 싶다.