7-A 질문

Question

http://boj.kr/a80f8148b5c64f2b92e8dd8f09216ae2 재귀를 사용하지 않고 문제를 풀었고, 함수 dp의 값을 초기에 -1로 초기화해서 불가능한 방문의 경우에는 dp값이 -1로 유지되기 때문에 문제가 발생하지 않도록 코드를 짰는데 94%에서 오답처리가 됩니다. 어떤 부분이 문제인지 알고 싶습니다. 7-a 올려주신 코드에서 int& ref 를 사용하셨는데 레퍼런스를 사용하지 않고 int ref를 사용하니 시간초과가 뜨는 것을 확인할 수 있었습니다. 여기서 레퍼런스를 사용하는 이유와 어떤 상황에서 레퍼런스를 사용해야 하는지 궁금합니다. 감사합니다.

큰돌 · Answer

Feus님 답변 감사합니다. ㅎㅎ 첨언을 하자면 지금 if(a == 1)일 때 종료시키는 것 같은데 이 문제는 어떠한 지점이든 출발해서 다 돌고 그 시작한 지점으로 갔을 때의 최솟값을 구하는 문제입니다. 제 생각에는 이 코드가 그러한 점이 고려가 안되었다고 생각해요. 감사합니다.

Feus · Answer

레퍼런스 한 것과 안한 것은 아예 다릅니다. 해설코드로 말씀드리면 int &ret = dp[here][visited]; 이렇게 레퍼런스를 걸었을 때는 dp[here][visited] 이 주소를 참조를 한 후 ret = INF; ... ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]); 이 부분에서 dp[here][visited] 의 값이 변경됩니다   하지만 레퍼런스를 걸지 않고 하게 되면 dp[here][visited] 의 초기 값만 할당될 뿐이고 메모리 주소를 참조하지 않기때문에 변경되지 않아요