최단길이 길찾기 알고리즘에 대해 질문올립니다.
조회수 1626회
오랜 시간 붙잡고 있어도 전혀 진전이 없어 여러분의 도움을 구합니다.
2차원 배열 안에 k개의 컴포넌트를 잇는 문제입니다.
0은 지나갈 수 있는 길. *은 지나갈 수 없는 막힌 길, 숫자(1,2,3,4,5등등)은 최단길이로 이어야할 components입니다.
숫자 사이의 길은 서로 cross 될 수 없습니다. 한번 숫자 사이를 이으면 그 길은 다시 못 지나간다는 뜻입니다.
인풋 ex)) 4 4 //인풋 행렬의 크기 알려줌 (row,col순) 행렬크기는 2<=row,col<=300 0 0 0 3 0 * 0 * 0 1 0 0 2 0 0 0
-> 1,2 (3,2),(3,1),(4,1) //경로 좌표 -> 1.3(3,2),(3,3),(2,3),(1,3),(1,4)
이 인풋에서는 1-2와 1-3을 잇는게 최소루트입니다.
인풋 숫자 범위는 2<=k<=5입니다. k=2일때는 BFS을 통해서 찾으면 되는 간단한 문제인데.. k가 5에 가까워질수록 엄청난 경우의 수들이 있습니다.. 한 번 간 길은 다시 갈수 없다니까 문제가 엄청 복잡해지네요..
*2* *0* *0* *0* 010030 0***0 000000
이런 경우의 수도 있고..
001000002 000000000 000000300 400000005
이런 무지막지한 경우도 생각할려니까 머리가 너무 아픕니다. 여러분의 피같은 조언을 달게 받아들이겠습니다. 감사합니다.
p.s. 주위에서는 bfs,최소스패닝트리,이진트리,희소행렬,위상정렬 등등을 이용하면 된다는것같은데... 교수님 저는 1학년입니다..
댓글 입력