목록경로 찾기 (1)

-

floyd warshall :: 백준 :: 경로 찾기 :: 11403

경로 찾기 11403https://www.acmicpc.net/problem/11403 [문제 풀이] 이 문제를 푸는 방법은 여러 가지가 있다. 나는 bfs, dfs, 플로이드 와샬 알고리즘 중 플로이드 와샬 알고리즘을 이용해 풀었다.플로이드와샬 알고리즘은 형태가 정해져있기 때문에 모든 경로를 탐색하는 문제에 적용하기 쉬운 것 같다. 1. 모든 입력은 0과 1로 이루어져있다. 나는 입력을 받은 후 int형으로 바꾸지 않고 String형 그대로 map에 저장했다. 2. 정점 r에서 k로 가는 경로가 존재하고, 정점 k에서 c로 가는 경로도 존재한다면 정점 r에서 c로 가는 경로 또한 존재한다고 볼 수 있기 때문에 map[r][c]를 1로 설정해 주면 된다. 3. 탐색을 모두 마치고 출력하면 끝. 12345..
알고리즘/탐색 2016. 11. 3. 12:51
Prev 1 Next