본문 바로가기

그래프

(3)
그래프이론 - 섬의 개수(백준 4963번) 1. 그래프 이론 - 섬의 개수 (백준 4963번) 2. 그래프 이론을 이용한 문제 풀이1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162package _317324; import java.util.Scanner; public class Baekjoon4963NumberofIsland { static int count; static int[] dx= {-1,-1,0,1,1,1,0,-1}; static int[] dy= {0,1,1,1,0,-1,-1,-1}; static int[][] map=new int[50][50]; static int height..
위상정렬(백준 2252번 줄세우기) 1. 위상정렬위상정렬의 조건위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다. 진입차수를 이용한 위상정렬 1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.(방향 그래프 완성)2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)3. indegree가 0인 일을 모두 찾아 큐에 넣는다4. 큐에서 정점 하나를 꺼낸다.(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.7. 큐가 빌 때까지 ..
그래프 DFS 와 BFS 그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색) 1. 시작전그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다. 2.DFS(깊이우선탐색) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182package graph; import java.util.Stack; public class DFS { class Vertex{ pu..