본문 바로가기
728x90

전체 글139

[백준1012] 유기농 배추[java] 앞에서 풀었던 아파트 번호 붙이기와 매우 유사한 문제였다. 배추를 표시할 map과 방문했는지를 확인하기 위한 check를 이차원 배열로 만들고 위, 아래, 오른쪽, 왼쪽을 봐야하므로 dx와 dy를 만들어둔다dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0}; 그리고 for문을 이용해 배추가 있는 곳은 map에서 1로 만들어 주고 방문하지 않고 map에서 1이면 dfs메소드를 통해 근처의 방문 여부를 확인해 주면 된다. 코드 package baekjoon; import java.util.Scanner; public class organic_cabbage { static int[][] map; static boolean[][] check; static int cnt=0; public stati.. 2021. 3. 23.
[백준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.
728x90

티스토리툴바