알고리즘/DFS12 [백준 1967] 트리의 지름 / 자바 / DFS 문제 레벨: G4알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/19671 번째 시도: 실패 [깨달은 점]dfs는 리턴값이 void이고 전역변수를 고치는 게 구현하기 편함 리턴값이 int면 구현하기 까다로움[알고리즘 설명]지름의 중심점이 될 수 있는 노드는 자식을 2개 가지고 있는 노드이다.그래서 중심점이 될 수 있는 노드들을 dfs하며 답을 업데이트해간다.dfs는 루트노드에서 양갈래로 찢어져 가장 각각 가장 긴 길을 구한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayL.. 2024. 6. 20. [백준 1987] 알파벳 / 자바 / 백트래킹 문제 레벨: G4알고리즘: 백트래킹풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/19871 번째 시도 백트래킹 기본적인 문제굳이 설명을 적지 않겠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;public class Main { static int ans = Integer.MIN_VALUE; static boolean[][] visited; static int[] dx = {1,0,0,-1}; static int[].. 2024. 6. 19. [백준] 감시 / 자바 문제 레벨: G3알고리즘: 완전탐색 풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/156831 번째 시도: 실패 [알고리즘 선택 과정]각 cctv마다 방향 설정이 중요합니다그렇다면 각 cctv의 방향을 무슨 기준으로 놓아야 할까요주장: 각 CCTV마다 칸을 많이 차지하는 방향으로 반론: A가 칸이 많이 차지하는 방향, B가 칸이 많이 차지하는 방향으로 설정했는데 A,B가 겹치는 것이 많은 상황을 가장해보자.(주장 답안)0 0 #0 0 2(A)0 0 #0 0 2(B)0 0 #(정답 답안)0 0 0# # 2(A)0 0 0# # 2(B)0 0 0 그래서 이 주장은 옳지 않습니다. 패스그렇다면 완전탐색으로 각 CCTV의 모든 방향마다 확인해.. 2024. 5. 30. [백준] 치킨배달/ 자바** 문제 레벨: G5알고리즘: DFS+조합 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/15686 1 번째 시도 여느 BFS 문제랑 같다 생각하고 작성하였다import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set;//String[] s = br.readLine().split(" ");//Integer.parseInt(br.readLine());//int N = Inte.. 2024. 5. 21. [백준] 연구소/자바 문제 레벨: G4알고리즘: BFS, DFS풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/14502 1 번째 시도 벽을 세우는 규칙이 안 보이는 것 같다결국 완전탐색 선택또 하나, 힌트인 것은 입력 값 N,M이 8이하이다. 결국 완전탐색을 해도 된다는 소리이다.얉은 복사 필수!!1. 얕은 복사 : 복사한 배열이 원래 배열의 '주솟값'을 가져옴2. 깊은 복사 : 복사한 배열이 원래 배열을 '그대로' 가져옴 dfs로 벽을 세울 경우의 수를 탐색하고 3개의 벽을 세우면 bfs함수 호출하여 바이러스를 퍼트리기바이러스를 퍼트릴 때 원본배열에서 퍼트리는 것이 아니라 얕은 복사를 한 배열에 퍼트린 것이다. import java.io.BufferedReader;im.. 2024. 5. 8. [백준] 트리의 지름/자바 문제 레벨: G2알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11671 번째 시도 dfs를 통해 임의의 정점 하나에서 가장 먼 정점을 구한다. (임의의 정점은 아무거나 상관없다.)dfs를 통해 구한 정점으로 부터 가장 먼 정점까지의 거리를 구한다.import java.util.*; public class Main { static ArrayList[] list; static boolean[] visited; static int max = 0; static int node; public static void main(String args[]) { Scanner scan =.. 2024. 5. 6. [백준] 적록색약/자바 문제 레벨: G2알고리즘: DFS 풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/100261 번째 시도 할 일 배열 초기화적록색맹x 일때 dfs적록색맹o 일때 dfs인접해있는 요소를 비교하는 문제일 때는 방향 설정 배열을 쓰는 것이 Point!dfs함수의 for문과 main함수에서 for문을 짤 때 헷갈릴 수도 있다.dfs함수는 동,서,남,북 방향으로 주어진 글자랑 같은 게 무엇인지 찾는 것이고 main함수의 for문은 전체배열을 순서대로 순회하는 것이다 문제가 카드의 경우의 수를 구하는 경우라면 main함수의 for문은 없을 것이다. dfs 함수내에만 존재할 것이다.dfs함수에서 전체 배열을 순서대로 순회하기 때문에 main함수에서 전체.. 2024. 5. 5. [백준] 트리/자바 문제 레벨: G5알고리즘: DFS풀이시간: 2시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/10681 번째 시도 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { static ArrayList list = new ArrayList(); static boolean[] visited; static int answer = 0; public static void main(String[] .. 2024. 5. 4. [백준] DFS와 BFS/자바 문제 레벨: S2알고리즘: DFS, BFS풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/12601 번째 시도 가장낮은 숫자부터 탐색해야 한다하니 인접행렬로 그래프 구성dfs 메소드 작성법visted[] = true할 일for문으로 dfs 재귀호출import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static StringBuilder sb = new String.. 2024. 5. 3. 이전 1 2 다음
