[코딩테스트] PrimePath 문제 (c++)

알고리즘 문제 중에 이런 문제가 있습니다.

 

특정한 4자리 숫자 2개 a, b가 있습니다.

숫자 a의 한 자리 숫자만을 변경해서 b를 만들되, 이 때

거쳐가는 숫자들은 모두 소수여야 합니다. 

몇 번을 거쳐야만 숫자 b를 만들 수 있는지 구하는 문제입니다.

 

예를들면, 1033 에서 8179 로 바꾸는 경로를 생각해봅시다.

 

1033
1733
3733
3739
3779
8779
8179

 

이렇게 여섯 단계를 거쳐서 8179로 만들 수 있겠죠.

중간에 1733부터 8779는 모두 소수입니다.

 

이 문제를 처음 접하고 저는 어떻게든 해서 문제를 풀 수 있게 됬는데

다른 사람의 글을 보니 Breadth-first search 또는 Dijkstra’s algorithm algorithms

알고리즘을 사용해서 풀 수 있다고 하더라구요.

 

저는 아직 공부를 많이 못해서 위의 알고리즘은 모르고 풀었습니다;

 

저는 C++언어를 사용했고, C++ STL의 queue와 Pair, vector를 사용했습니다.

경로가 담긴 vector와 횟수를 담은 Pair를 Queue에 넣어서 문제를 해결했습니다.

 

 

아래는 코드입니다.

 

 

함수 isPrime은 단순히 입력값 n이 소수인지 판단합니다.

별다른 알고리즘은 사용하지 않았습니다.

 

함수 oneDigit은 두 int 값을 받아서, 두 수가 '한' 자리만 차이가 나는지 비교하고,

'한'자리만 차이가 나면 true를 반환합니다.

 

문제 해결을 위해서는 어떤 두 수가 한자리만 차이가 나는지 확인해야겠죠?

 

 

 

listPrime 함수는 두 int 값을 받아서 두 수 사이에 모든 소수들의 리스트들을 반환합니다.

 

listOneDigit 함수는 어떤 int 값과 int를 담고 있는 벡터를 입력값으로 받는데,

이 벡터에 담겨져 있는 모든 수들을 비교해서 '한'자리만 차이가 나는 수들 찾아서 반환합니다.

여기서 한자리만 차이가 나는지 체크하는 oneDigit 함수를 사용했습니다.

 

 

 

 

메인 함수인 PrimePath 함수인데요, from 값은 시작점, to 는 도착점입니다.

 

먼저 소수경로와 거쳐간 횟수를 담을 큐를 선언하고, 처음값을 넣어줍니다.

그다음 primes 변수에 앞서 만들었던 listPrime으로 1000 부터 9999 사이에 소수들을 집어넣어줍니다.

어차피 네자리니까요.

 

그다음 큐의 가장 위에 있는 소수 경로의 마지막이 목적지에 도착했는지 확인하고,

도착할 때 까지 while문을 실행하는데요.

 

현재 보고 있는 경로의 마지막에 있는 수가 이동할 수 있는 수들을 candidate에 넣습니다. (후보군입니다)

후보군이 없다면 무시하고, 그렇지 않다면

후보군에 있는 모든 수들을 검사하는데, 이 때 후보군이 이미 거쳐간 경로에 포함된다면 무시하고,

그게 아니라면 그 후보군을 포함한 새로운 경로를 큐에 넣어줍니다.

이때 큐에 넣어줄때 pair에 두번째 값을 1 증가시키고 넣어주어야 겠죠? 왜냐하면 이동 횟수니까요.

 

그리고 후보군을 모두 살펴보고 나면 현재 보고있는 경로를 pop 해줍니다.

 

 

그래서 저의 경우 위와 똑같은 경우 1033과 8179를 넣어서 실행해봤습니다.

 

 

시간이 꽤 걸리더군요! 솔직히 다른 케이스들은 시도안해봤지만, 되길 빌어야겠죠 ^^;

 

후보군을 생각해보니 그래프가 떠올랐고, 그래프를 처리할 생각을 하다보니

큐가 생각나더군요.

다음에는 위에 두 알고리즘을 배워서 써먹어봐야겠습니다.

 

 

만약 위 풀이가 잘못됬다거나 궁금하신 점들이 있으시다면 댓글달아주세요~

 

 

--------------------------------------------------------------------------------

p.s) 제가 했던 방식이 BFS였군요.