그래프
-
백준 5567번 결혼식 [그래프] :: 마이구미알고리즘 풀이/그래프 2017. 4. 10. 14:21
이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.그래프를 통해 문제를 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.상근이의 친구상근이의 친구의 친구위의 2가지의 조건에 ..
-
플로이드 와샬 알고리즘 :: 마이구미알고리즘 2017. 1. 27. 22:36
이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다.동적계획법을 기반으로 구현되는 알고리즘이다.위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다.시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다.코드를 보면 굉장히 짧고 간단하다. for (int k = 0; k <..
-
백준 10451번 순열 사이클 :: 마이구미알고리즘 풀이/그래프 2017. 1. 22. 15:28
이번 글은 백준 알고리즘 10451번 "순열 사이클" 을 다뤄본다.백준 알고리즘 10451번 순열 사이클 문제https://www.acmicpc.net/problem/10451DFS, BFS 관련 글.http://mygumi.tistory.com/102 위 그림처럼 사이클 개수를 찾는 문제이다. (방향이 존재함으로 방향 그래프)정점들이 연결되어 하나의 그래프를 이루는 것을 그래프의 연결 요소라고도 말한다.즉, 연결 요소의 개수가 순열 사이클의 개수와 같은 의미이므로, 연결 요소를 구하면 되는 문제이다. 이 문제의 이름이 보면, 순열 그래프이다.순열의 정의 상 숫자는 중복으로 입력되지 않는다고 한다.그렇다는 건, 그래프가 한개 이상이 존재하지만, 주어지는 그래프는 모든 정점에 연결된 사이클이 있는 그래프라..
-
[그래프] DFS와 BFS 구현하기 :: 마이구미알고리즘 2017. 1. 19. 22:15
이번 글은 자료구조 중 그래프를 다뤄본다.백준 알고리즘 1260번을 통해 진행하니 참고하길바란다. 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E) 그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다. 무방향 그래프와 방향 그래프가 있다.말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.여기서는 무방향 그래프를 기준으로 다뤄볼 것이다. 그래프의 탐색에 있어 DFS, BFS 방식이 있다.깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 ..