GAMEGAME

나름 DP를 생각하면서 풀었는데
BFS로 풀었다봐도 무방한거 같네요 걍..ㅠ
완전 DP로 푸는데까지 생각이 도달하는게 힘든 것 같네요

BFS와 다이나믹 테이블을 섞어서 풀었는데 그럼 이건 DP로 풀었다고 볼 수 없는건가요??

선생님 풀이와 다른점은
1. 출발점만 초기화 시켰다는 것
2.위쪽과 왼쪽에서 올 수 있는 경우 일단 더해보고 에너지가 더 작은 값을 dy테이블에 할당시켰다는 것입니다.
일단 dynamic테이블에 저장하면서 사용했긴 했는데.. 선생님 풀이를 보니 그냥 단순 BFS로 풀었다봐도 무방한 것 같긴 한데. 결과적으로 이런 풀이는 DP로 풀었다고 볼 수 없는거죠?

유재용님이 말씀하신 것처럼 i가 1인 상태에서 j가 2번 돌게되면 0,5,4,무한대,무한대인 상태인데 그 다음 j가 3번째로 돌 때, 2->3 경로를 계산하면 dist[2]+w < dist[3]이 되는데 이 때, dist[2]는 무한대가 아니라 5로 계산된 값이라서 결국 dist[3]이 2로 릴렉스됩니다. 그럼 결국 i가 1인 상태임에도 불구하고 1->2->3을 거친 값이 dist[3]에 들어가게 됩니다. 저는 "i가 1"이다의 의미를 "시작 노드로부터 한 번의 경로로 갈 때"로 이해했습니다. 제가 이해한 것이 틀렸는지 잘 모르겠습니다.
설명해주신대로 값이 릴렉스 되려면 dist를 인접행렬로 만들거나 해서 이전 경로횟수(0번)의 인덱스 값(2)에 +w를 해주어야할 것 같습니다 그래야 무한대+(-3) 이 되어 dist[3]이 4로 릴렉스 될 것 같습니다.
설명해주신 흐름과 코드의 흐름이 약간 매치가 안돼서 혼란이 오는 것 같습니다. 다시 한 번 정확하게 짚어주시면 감사드리겠습니다.

벨만포드 알고리즘

1. 혹시 코드에서 반례나, 비 효율적인 부분이 있는지 말씀해주시면 감사드리겠습니다. 아직 정답을 확인할 수 없는 환경이라서, 부탁드리겠습니다.

2. 그리고 처음에는 선생님의 답변과 비슷한 방법으로 생각했었는데, for(i = 0; j <s; j++) if(c[j]==a) pos = j;를 하는 과정이 비효율적이라고 생각해서 배제했었습니다.

3. 리뷰 부탁드리고, 선생님 답변으로 또 한 번 공부하도록 하겠습니다. 좋은 강의 감사합니다.

GAMEGAME

Posts