최단길이 길찾기 알고리즘에 대해 질문올립니다.

조회수 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학년입니다..

  • 인풋은 0003/0***/0100/20*0입니다. 올리고 나니까 제대로 안보이네요. 죄송합니다. 김상훈 2017.10.16 20:49

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)