풀이 어떤 노드에서 가장 먼 노드는 트리 지름에 해당하는 두 노드 중 하나인 것이 문제 풀이의 핵심이다. 즉, 처음에 임의(이 문제에선 1)의 노드에서 가장 먼 노드를 찾고(트리의 맨 끝을 찾는 다는 말), 그 노드에서 또 가장 먼 노드를 찾으면(트리의 반대쪽 맨 끝을 찾으면), 그 거리가 트리의 지름인 것이다. 각각의 노드들을 class로 관...
백준 2178번(미로 탐색)[JAVA]
풀이 2차원 그래프의 완전 탐색 문제이다. BFS를 사용하여, 도착 위치에 처음 도달했을 때의 깊이를 구하면 된다. 소스 코드 import java.util.*; import java.io.*; public class 미로탐색 { static boolean[][] visited; static int[][] arr; static int ...
백준 1260번(DFS와 BFS)[JAVA]
풀이 말 그대로 dfs와 bfs를 구현하면 된다. 각각의 함수에서 dfs는 함수를 호출했을 때 입력된 인자를, bfs는 while문의 루프가 돌아갈 때 입력된 인자를 출력하는 것이 문제에서 구하고자 하는 수행 순서이다. 방문할 수 있는 정점이 여러개인 경우에는 정점 번호가 작은 것을 먼저 방문하라 하였으므로, 그래프를 오름차순으로 정렬한 후에 d...
백준 1012번(유기농 배추)[JAVA]
풀이 2차원 배열에서 dfs를 실행할 때, dfs가 재귀호출을 하는 것이 아닌, main함수에서 dfs를 몇번 호출하는지를 세면 된다. main 함수 안의 for문 안에 cnt변수를 증가시켜주는 방법으로 간단하게 풀 수 있다. 소스 코드 import java.util.*; public class 유기농배추 { static boolean[]...
백준 2606번(바이러스)[JAVA]
풀이 1번 컴퓨터가 바이러스 걸렸을 때, 연결되어있어서 같이 바이러스에 걸리게 되는 컴퓨터의 수는, dfs(1)을 하였을 때 방문되는 노드의 개수와 같다. 즉, visited 배열에서 true의 개수를 세어주면 된다. 결과에서 result-1을 해주는 이유는 1이 포함되어 있기 때문이다. 소스 코드 import java.util.*; pub...
백준 2023번(신기한 소수)[JAVA]
풀이 자릿수를 n까지 하나씩 늘려가며 모든 소수를 찾는 완전 탐색 문제이다. 즉, dfs를 활용하여 풀 수 있다. dfs에 입력한 수가 소수라면, 입력한 수에 * 10을 하여 자릿수를 늘리고, 그 뒤에 for문을 통해 수를 이어붙힌 후, 소수인지 판별한다. 그리고 그 수가 소수일 경우, 그 수를 다시 dfs에 입력한다. 자릿수가 늘어났으므로, 자...
백준 13023번(ABCDE)[JAVA]
풀이 A - B, B - C, C - D, D - E 관계를 가진 A,B,C,D,E가 존재하는지 알아본다는 것은, DFS에서 A로 시작하여 DFS(B) 호출할 수 있고, B에서 DFS(C), C에서 DFS(D), D에서 DFS(E)를 호출할 수 있는 그래프이다. 즉 DFS(A)부터 탐색의 깊이가 5가 되면 이 조건을 만족할 수 있다. 탐색의 깊이...
백준 11724번(연결 요소의 개수)[JAVA]
풀이 그래프 탐색 문제이다. DFS를 활용하면 되며, 연결 요소의 개수가 DFS의 실행 횟수인게 핵심이다. 소스 코드 import java.util.*; import java.io.*; public class 연결요소의개수 { static ArrayList<Integer>[] arr; static boolean visited[]...
백준 11399번(ATM)[JAVA]
풀이 연습 삼아 삽입 정렬로 푼 코드이다. 실제로 삽입 정렬은 코딩 테스트에서 효율적이지 않다. 선택 정렬도 마찬가지다. 선택 정렬과 삽입 정렬, 버블 정렬은 시간 복잡도가 O(n^2)이기 때문에, 이 문제나 백준 1427(소트인사이드)와 같이 시간 제한이 널널하면 쓸 수는 있지만, 널널하다고 해서 효율적인 정렬 방법은 아니기 때문에 그냥...
백준 11004번(K번째 수)[JAVA]
풀이 n이 5,000,000이고 시간 제한이 2초다. 즉, O(nlogn)인 정렬을 사용해야 한다. 가장 간단하게 정렬할 수 있는 Arrays.sort()(퀵 소트)를 사용하여 풀었다. (사실 귀찮아서…) 이 문제도 Scanner를 쓰면 시간 초과가 뜬다!!!!BufferedReader를 사용하도록 하자! 소스 코드 import java...