백준/BFS & DFS (10) 썸네일형 리스트형 백준 24483 자바 알고리즘 수업 - 깊이 우선 탐색 1~4를 풀었다면 수월히 풀 수 있습니다. import java.util.*;import java.io.*;public class Main { static int N,M,start; static int[] visit; static ArrayList[] list; static long result = 0; static int[] arr; static int cnt = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str.. 백준 24481 자바 import java.util.*; import java.io.*; public class Main { static int N,M,start; static int[] visit; static ArrayList[] list; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); start .. 백준 24480 자바 새해 기념으로 한 문제만 풀겠습니다.. 술 먹고 와서 너무 힘듭니다.. 전에 풀었던 DFS문제이고 내림차순으로만 변경해주면 됩니다. 1 - 4 2 2 - 4 3 1 4 - 4 2 4 - 3 2 1 내림차순을 하면 이런 식으로 Arraylist에 넣어집니다. 그럼 노드는 1 4 2 3 이렇게 형성된다고 치면 순서는 1 - 1번째 2 - 4번쨰 3 - 3번째 4 - 2번째 5 - 0 이렇게 연결이 됩니다. 직접 그려서 해보시면 이해가 쉽습니다. 인접 정점을 내림차순으로 방문하니까 1에서 연결된 4, 2에서 4를 먼저 방문을 하고, 4와 연결된 3, 2중에서는 3을 먼저 방문을 합니다. 그리고 나머지 2를 방문하게 됩니다. import java.util.*; import java.io.*; public cla.. 백준 24479 자바 DFS 문제이고 전에 푼 bfs 문제와 유사합니다. DFS는 재귀를 이용하기 때문에 풀이가 좀 간단해지네요. 아래 DFS에 대해 설명하자면 check[] 배열은 방문을 했는지, 안 했는지를 확인하고 arr[] 배열은 방문 순서를 담는 배열입니다. 입력을 보면 1 - 2 4 2 - 1 3 4 3 - 2 4 4 - 1 2 3 이렇게 ArrayList가 만들어지고 노드는 1 2 4 3 이런 식으로 만들어집니다. 먼저 start로 1이 들어오면, for문에서 i는 list[1]의 2,4를 확인합니다. 1. if (!check[2]) 이므로 DFS(2)를 불러옵니다. 그럼 DFS(2)가 실행되면서 arr[2] 는 2가 되겠죠. 2. for문이 int i : list[2] (3,4)를 돌게 되고 3을 먼저 가니까 .. 백준 11725 자바 BFS로 풀었고 트리의 개념만 알면 쉬운 문제입니다. 루트인 1부터 입력 받은 대로 트리를 그려보면 트리의 부모를 찾을 수 있고 아래 BFS를 보면 1번을 처음에 넣으면 for문에서 int i가 list[1] (6,4)를 돌고 이 6,4가 1의 자손이라는 것을 알 수 있습니다. 그럼 그래프는 1 6 4 이렇게 만들어지겠죠. 그럼 이 6과 4를다시 queue에 넣고 부모를 저장하는 배열 parent[6], parent[4]에 1을 넣었습니다. 그리고 다시 queue를 돌면 이제 6과 4가 부모가 되겠죠. 그러면 for문에서 1 6 4 3 2 7 이렇게 만들어집니다. 6과 3이 연결, 4와 2,7이 연결된 것입니다. 이렇게 for문에서 int i가 자손이 되고, q가 부모가 된다는 것을 이용하면 됩니다. i.. 백준 11724 자바 BFS 풀이입니다. 아래 BFS 메서드는 기존과 동일합니다. 문제는 연결 요소를 구하는 것인데 연결 요소는 쉽게 말하면 나누어진 각각의 그래프입니다. 즉, 몇 묶음으로 나뉘었는지를 구해야 합니다. 문제 입력을 보면 예제 1은 1 - 2 - 5 , 3 - 4 - 6 으로 2개가 나옵니다. 하지만 BFS 메서드를 보면 처음 입력 1이 들어가면 2, 5는 탐색할 수 있지만 3,4,6은 탐색을 못 합니다. 그래서 BFS 메서드는 가만히 냅두고 위에서 반복문을 이용해서 cnt를 구했습니다. 1번부터 N번까지 반복이지만 어차피 BFS를 돌면서 방문하면 true로 바뀌게 되니까 총 BFS 몇 번 도는지 (몇 개의 묶음으로 나뉘는지)를 셀 수 있습니다. import java.util.*; import java.io.*.. 백준 2644 자바 BFS를 이용하여 풀었습니다. 간단하게 설명하자면 촌수 관계가 Node 역할을 합니다. 이것을 ArrayList에 담고 num과 num1이 몇 촌 사이인지 계산을 해야 합니다. 아래 BFS 구현은 일반적인 BFS문제와 비슷하지만 추가할 것은 int[] arr 배열을 이용해서 촌수 관계를 기록해놔야 합니다. 좀 쉽게 말하자면 어차피 3과 7의 관계를 볼 때 가까운 촌수부터 점점 멀어지므로 이전의 arr[q]에 + 1을 해주는 방식입니다. 그리고 우리가 찾아야 할 num1과 q가 같다면 그대로 끝을 내주고, 다 찾아봤는데도 못 찾으면 기존의 result값인 -1을 출력하면 됩니다. import java.util.*; import java.io.*; public class Main { static ArrayL.. 백준 2606 자바 백준 DFS, BFS 문제이고 풀이는 2개 다 가능합니다. 근데 저는 BFS 공부 중이라 BFS로 풀었습니다. 여기서 생각해야 할 점은 바이러스가 걸린 컴퓨터를 구하는 cnt를 언제 증가시켜줘야하냐? 입니다. 단순히 코드만 암기하면 안 되고 bfs 알고리즘에서 어느 부분이 감염되는 컴퓨터 역할을 하는지 생각해야 합니다. 문제의 그림 1을 보면, 1번이 걸리면 2,3이 걸리고 2번과 연결된 5번, 5번과 연결된 6번이 걸립니다. 즉, 2 3 5 6을 카운팅해서 4개가 나오는 겁니다. 자 그러면 이를 bfs 알고리즘에 접목시켜보면 1번과 연결된 2,3 컴퓨터를 발견할 때 count를 올려줘야 합니다. 마찬가지로 2번과 연결된 5번, 5번과 연결된 6번을 발견할 때도 count를 올려줘야 합니다. import.. 이전 1 2 다음
