백준 1963. 소수경로 [실패]

1.실패 원인

우려했던 문제가 두 가지 터졌다. 첫 번째는 배웠던 알고리즘임에도 불구하고 정확히 구현이 불가능했다는 점 (에라토스 테네스의 체, bfs), 두 번째는 완전탐색을 가장한 BFS 문제임에도 해당 문제가 어떤 유형의 알고리즘을 적용해야하는지 알지 못했다는 점이다. 그리고 만약 위의 두 가지 경우를 다 알았다 하더라도 구현을 제대로 하지 못했을 것 같다.

 

2.참고 코드

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-1963-%EC%86%8C%EC%88%98-%EA%B2%BD%EB%A1%9C

백준 1963 소수 경로

 

3. 해결 방안

직관적으로 경로 문제임을 들어내지 않는 문제에 대해서 그래프 문제로 인식을 하지 못했다. 위의 문제와 다음 포스팅 할 문제에 대해서 공통적인 부분이 있는데 특정 숫자에서 특정 숫자로 갈 때 몇번의 경로를 거치느냐 혹은 몇번 이동을 해야하느냐에 관한 것이다. 위의 참고 코드 블로그에서도 설명되어 있지만 무엇을 노드로 보고 무엇을 경로로 보느냐에 따라 해당 문제를 BFS 문제로 인식할 수 있게끔 해주는 것이다.

 

몇번의 경로.. 이동 이런 말을 썼지만 문제에서는 이런 단어를 사용하지 않는다. 본인이 생각해서 판단해야 할 것 같다.