728x90 분류 전체보기138 [백준2667] 단지번호붙이기 [ java] dfs로 문제를 풀어보았다. 방문했는지를 확인하기 위한 visit이차원 배열을 만들었다. 코드 package baekjoon; import java.util.Arrays; import java.util.Scanner; public class apart_num { public static int dx[] = {0,0,1,-1}; public static int dy[] = {1,-1,0,0}; public static int[] aparts = new int[25*25]; public static int n; public static int apartNum = 0; public static boolean[][] visit = new boolean[25][25]; public static int[][] ma.. 2021. 3. 22. [백준2606] 바이러스 [java] 이 문제는 dfs나 bfs나 상관없다고 생각하지만 bfs를 사용하면 큐를 이용해야 할 것 같아서 dfs를 사용했다. 트리를 표현하기 위해서 연결리스트방법을 사용했다 리스트안에 리스트를 넣어서 연결된 노드들을 표현했다. 또한 1부터 시작하므로 리스트에 크기를 1~주어진 크기보다+1을 해줬다. 코드 package baekjoon; import java.util.ArrayList; import java.util.Scanner; public class virus { public static ArrayList list[]; public static boolean check[]; static int cnt = 0; public static void main(String[] args) { Scanner scan = .. 2021. 3. 22. [백준1260번] DFS와 BFS 간단하게, 깊이우선탐색(DFS) 는 한 노드의 관해서 깊게 들어가면 된다. 따라서 한 노드를 방문했었는지를 기록하며 그 노드와 연결된 노드를 기준으로 다시 DFS메소드를 호출하면 된다. 너비우선탐색(BFS)는 한 노드에서 연결된 모든 노드를 방문하는 것이므로 큐를 이용하여 큐에서 빼낸 노드와 연결되며 방문하지 않은 모든 노드를 큐에 넣고 큐가 빌때까지 반복해주면 된다. 코드 package baekjoon; import java.util.*; public class dfs_bfs { public static boolean[] check; public static ArrayList list[]; public static void main(String[] args) { Scanner scan = new Sca.. 2021. 3. 18. 그래프 알고리즘 - 4 DAG(Direct Acyclic Graph) - DAG는 방향 사이클이 없는 방향 그래프 - 예 : 작업들의 우선순위 - DAG에서 노드들의 순서화 v1,v2,v3,....vn, 단, 모든 에지(vi,vj)에 대해서 i indegree = 0 : 들어오는 개수가 없다. 위상정렬 알고리즘 1 문제 - indegree가 0인 노드를 찾기 위해서 모든 노드의 indegree를 알아야 한다. - 진출간선을 제거했을 때 어떤 방법으로 구현할 것인지 어려움 위상정렬 알고리즘2 - dfs-ts는 보통의 깊이 우선탐색이랑 같지만 마지막 줄이 추가됨 - 처음에 마지막으로 도달한 노드는 outdegree가 없다 - 위상정렬 1에서는 가장 먼저 나오는 노드를 찾는 알고리즘이라면 - 위상정렬 2에서는 가장 마지막에 나오는 .. 2021. 3. 17. 그래프 알고리즘 - 3 깊이우선순회(DFS) 1. 출발점 s에서 시작 2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited노드가 존재하면 그 노드로 간다 3. 2번을 반복 4. 만약 unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다. 5. 다시 2번을 반복한다. 6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 수도코드 - 그래프가 disconnected이거나 혹은 방향 그래프라면 dfs에 의해서 모든 노드가 방문되지 않을 수도 있음 - DFS를 반복하여 모든 노드 방문 시간복잡도 : O(n+m) * 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다. 2021. 3. 17. 그래프 알고리즘 - 2 그래프 순회(Graph Traversal) - 순회 : 그래프의 모든 노드들을 방문하는 일 - 대표적 두 가지 방법 BFS (Breadth-First search, 너비우선순회) DFS ( Depth-First Search, 깊이우선순회) 너비우선순회(BFS) - BFS 알고리즘은 다음 순서로 노드들을 방문 L0 = {s}, 여기서 s는 출발 노드 L1 = L0의 모든 이웃 노드들 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ..... Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 큐를 이용한 너비우선순회 -큐가 빌때까지 반복 - 탐색이 된 노드는 큐에서 제거 - 그 이웃한 노드들 큐에 삽입 후 방문했다고 체크 - 큐에 1을 넣는다 | 1 - 1을 제거하면서 큐에 인접한 2,3을 .. 2021. 3. 16. 이전 1 ··· 16 17 18 19 20 21 22 23 다음 728x90
