인접행렬
-
백준 5567번 결혼식 [그래프] :: 마이구미알고리즘 풀이/그래프 2017. 4. 10. 14:21
이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.그래프를 통해 문제를 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.상근이의 친구상근이의 친구의 친구위의 2가지의 조건에 ..
-
[그래프] DFS와 BFS 구현하기 :: 마이구미알고리즘 2017. 1. 19. 22:15
이번 글은 자료구조 중 그래프를 다뤄본다.백준 알고리즘 1260번을 통해 진행하니 참고하길바란다. 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E) 그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다. 무방향 그래프와 방향 그래프가 있다.말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.여기서는 무방향 그래프를 기준으로 다뤄볼 것이다. 그래프의 탐색에 있어 DFS, BFS 방식이 있다.깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 ..