백준56 [백준] 내리막길/자바 문제 레벨: G4알고리즘: DFS + DP 풀이시간: 40분 힌트 참조 유무: 유https://www.acmicpc.net/problem/15201 번째 시도 1. 먼저 (0,0) 위치에서 시작하므로 dp[0][0]값을 0으로 초기화한다.2. (0,0) 위치에서 상하좌우로 이동하면서 map[x][y] > map[nx][ny]인 위치에 대해서만 DFS 메소드를 재귀호출3. 재귀호출을 통해 (M-1, N-1)위치에 도달하는 경로의 개수를 찾는다.4. 이렇게 찾은 경로의 개수를 dp[0][0] 값에 더해준다.5. 모든 이동 가능한 위치에 대해 위 과정을 반복6. dp[0][0] 값이 결정되면 해당 값을 리턴한다.위와 같은 과정을 거쳐서 dp[0][0] 값을 찾게 된다. 만약 dp[0][0].. 2024. 5. 13. [백준] 토마토/자바 문제 레벨: G5알고리즘: BFS풀이시간: 2시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7569 1 번째 시도 기존 bfs와 다른 점은 하나인 줄 알았다. 방향이 상,하가 추가 되서 총 6개를 탐색해야 된다는 점이다 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;public class Main { static int[] xx; static int[] yy; public stat.. 2024. 5. 12. [백준] 1로 만들기/자바 문제 레벨: S4알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/14631 번째 시도 귀여운 수준의 구현이어서 바로 작성해보았다import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int cnt = 0; .. 2024. 5. 9. [백준] 연구소/자바 문제 레벨: 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. [백준] 벽 부수고 이동하기/자바 문제 레벨: G3알고리즘: BFS 풀이시간: 1시간 20분힌트 참조 유무: 유https://www.acmicpc.net/problem/22061 번째 시도 벽을 언제 뽀갤 건지 한 번에 알 수 있나?NO근데 왜 dfs가 아니고 bfs 인가?dfs는 최단 경로를 찾는 것이 아니라 끝까지 탐색해서 경로를 찾는 것이기 때문에 첫 번째 도착한 것이 최단경로임을 보장하지 않는다. 최단 경로 찾기에 bfs가 적합하다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main.. 2024. 5. 7. [백준] 트리의 지름/자바 문제 레벨: 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 3 4 5 6 7 다음
