Better than alone

그래프 탐색과 관련된 알고리즘의 종류 Sample DFS(깊이 우선 탐색, Depth First Search) 내부적으로 스택을 사용한다. 1 1 → 2 1 → 2 → 3 1 → 2 → 3 → 4 1 → 2 → 3 → 4 → 5 1 → 2 → 3 → 4 → 5 → 6 1 → 2 → 3 → 4 → 5 → 6 → 7 시작점에서 시작하여 막다른 점이 나올 때까지 탐색한다. 막다른 점을 발견하면 되돌아 갈 길을 역추적(backtracking)하는 과정을 거친다. BFS(너비 우선 탐색, Breadth First Search) 내부적으로 큐를 사용한다. 1 1 → 2 1 → 2 → 7 1 → 2 → 7 → 8 1 → 2 → 7 → 8 → 3 1 → 2 → 7 → 8 → 3 → 6 1 → 2 → 7 → 8 → 3 ..

그래프(Graph) 기본 정의 정점(V: vertices)이라고 불리는 노드들의 집합과 간선(E: edge)이라고 불리는 정점 간의 선으로 이루어짐. (V,E)로 나타낸다. (5, 3) ⇒ 정점 5개, 간선 3개 사용 네트워크, 전자회로, 운송 방법(길찾기) 종류 방향을 가지는 그래프(Directed graph) 방향을 가지지 않는 그래프(Undirected graph) 순환 그래프(cycle graph): 첫번째 정점과 마지막 정점이 동일 비순환 그래프(acyclic graph) 트리 - 포레스트(forest), 신장트리(spanning), ..... 표현: 일반적인 인접 무방향 그래프 방향 그래프 무방향 가중(weight) 그래프 ⇒ 인접 매트릭스(인접 행렬)의 필요한 공간은 다음과 같다. : O($..

https://www.acmicpc.net/problem/2352 문제 도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오 입력 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 ..