https://www.acmicpc.net/problem/14938
여러번 도전했다..
1. 각 노드에서부터 파장 마냥 점점 퍼져나가면서 체크하면 될 것 같다는 생각에 BFS 를 먼저 택했었다.
그러자 치명적인 문제에 도달,, 단순 BFS로 들렀던 노드를 체크하는 경우
a->c 로 c 를 먼저 들르면
a->b->c 경로를 선택할 수 없게된다...
길별로 가중치가 달라서 a->c 보다 a->b->c 경로가 더 짧을 수 있는데, bfs 는 무조건 노드 사이에 간선 수가 적은걸 먼저 들르다보니까 아주 적절하지 않은 방법이었다고 판단된다.
bfs로 할려면 각 bfs 마다 여태까지 지나온 경로들을 다 저장해주고 지나왔던 노드를 다시 가지 않도록 관리해줘야할 것 같은데 이건 너무 비효율적이라고 생각돼서 방법 수정..
2. 플로이드와샬
플로이드 와샬로는 일단 각 노드에서 다른 노드로 가는 최단 거리를 구할 수 있음. 근데 거기에는 최단거리밖에 없잖아,,?? 이를 어떻게 사용해야할지,,, 막막해서,,,
이걸 약간 응용해보자면,,, 플로이드 와샬이 타겟 노드 X 에 대해서, A,B 노드에 대한걸 갱신하는데,,, 음... 모르겄다... 누구한테 물어봐야겠음...
1. 내가 푼 방법은 DFS
dfs는 한 경로를 쭉 탐색하니까 한 노드에서 도달할 수 있는 모든 경로를 다 탐색해볼 수 있다.
check 노드를 for loop DFS; 앞에서 1로, 뒤에서 다시 0으로 설정해주는 방법으로 모든 경로를 빠짐 없이 탐색해볼 수 있음.
근데 또 이미 들렀던 노드의 아이템을 또 주우면 안되니까 아이템을 주웠는지 말았는지 체크하는 배열을 따로 관리해주는 방식으로 해결했음.
수고했다 나자신!!
'Algorithem > 백준 PS with code' 카테고리의 다른 글
| 백준 #1562 : 계단 수 (0) | 2023.01.06 |
|---|---|
| 백준 #1509 팰린드롬 분할 : 점화식 (0) | 2023.01.06 |
| 백준 #1007 - 벡터매칭 : 절반은 더하고, 절반은 빼면 된다? (0) | 2023.01.06 |
| 백준 #16236 아기상어 - bfs 탐색 순서만으로는 해결할 수 없는 우선순위가 있다! (0) | 2023.01.06 |
| 백준 #9019 DSLR : 다음 세대에 어떻게 정보를 전달할것인가? (0) | 2023.01.06 |
