백준 #14938 - 서강그라운드 : 각 노드에서 범위 안에 속하는 모든 노드 체크하기

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으로 설정해주는 방법으로 모든 경로를 빠짐 없이 탐색해볼 수 있음.

근데 또 이미 들렀던 노드의 아이템을 또 주우면 안되니까 아이템을 주웠는지 말았는지 체크하는 배열을 따로 관리해주는 방식으로 해결했음.

수고했다 나자신!!