알고리즘 풀이/그래프
-
백준 10451번 순열 사이클 :: 마이구미알고리즘 풀이/그래프 2017. 1. 22. 15:28
이번 글은 백준 알고리즘 10451번 "순열 사이클" 을 다뤄본다.백준 알고리즘 10451번 순열 사이클 문제https://www.acmicpc.net/problem/10451DFS, BFS 관련 글.http://mygumi.tistory.com/102 위 그림처럼 사이클 개수를 찾는 문제이다. (방향이 존재함으로 방향 그래프)정점들이 연결되어 하나의 그래프를 이루는 것을 그래프의 연결 요소라고도 말한다.즉, 연결 요소의 개수가 순열 사이클의 개수와 같은 의미이므로, 연결 요소를 구하면 되는 문제이다. 이 문제의 이름이 보면, 순열 그래프이다.순열의 정의 상 숫자는 중복으로 입력되지 않는다고 한다.그렇다는 건, 그래프가 한개 이상이 존재하지만, 주어지는 그래프는 모든 정점에 연결된 사이클이 있는 그래프라..
-
백준 11403번 경로 찾기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 20. 23:42
이번 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 다뤄본다.이 문제는 그래프의 DFS, BFS 를 활용하는 문제이다.DFS, BFS - http://mygumi.tistory.com/102백준 알고리즘 문제 11403번 경로 찾기 - https://www.acmicpc.net/problem/11403 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 친절하게 문제에서 어떤 그래프인지 말해주고 있다.가중치가 없는 방향 그래프라고 명시되어 있다.그래프에 대한 글에서 무방향 그래프를 기준으로 다뤘었다.차이는 단지 방향이 있고 없고 차이뿐이다. // 무방향 그래프 인접행렬a[v1][v2] = 1;a[v2..