https://www.acmicpc.net/problem/1941  언뜻 보면 쉬워보였는데, 순수 dfs로 풀게되면 풀기 매우 까다롭다 1. 25C7로 25개의 좌표중에 7개를 고른 후, 2. S의 수가 4 이상인 좌표만 추린다.3. 그 좌표들을 dfs로 탐색하여 연결되어있는지 확인한다. 이정도인데, 1번은 조합을 구하는 dfs로 구하면 쉽게 구할수있고,2번도 조건문으로 쉽게 구할수있다.3번은 구현하면서 조금 해멨는데 연결만되어있는지 확인하기위해선 visited를 백트래킹할 필요없다는것을 생각하지못하였다.   import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { ..

https://www.acmicpc.net/problem/6987   처음에 스스로 풀었을때는 통과하긴 했지만 2000ms나 걸렸다. 처음 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;public class Main { static int[][] ans; static int[][] check; static boolean correct; static ArrayList list = new ArrayList(); static LinkedList set = new LinkedList(); public static..

https://www.acmicpc.net/problem/18428 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { static int N; static String[][] map; static boolean[][] visited; static ArrayList teacherList = new ArrayList(); static ArrayList list = new ArrayList(); static int c; static boolean ans = false; public static void main(String..

https://www.acmicpc.net/problem/1520  단순히 DFS 완전탐색으로 풀었지만 메모리 초과가 난다. 이유는 완전탐색DFS의 경우, 각 칸에서 최악의경우 O(N x M)번의 탐색을 해야한다.각 칸을 여러 번 중복해서 탐색할 수 있기 때문에, 최악의 경우 각 칸에 대해 O(N×M) 수행을 한다. 총 칸수는 N x M개이기 때문에 O((N x M) x (N x M)))의 시간 복잡도가 발생하게 된다. 즉 , 최악의경우 500 * 500 * 500 * 500 = 62,500,000,000 => 625억 이므로, 제한시간인 2초를 1초에 1억이라고 했을때 625억 >> 2억이므로 (625초 >> 2초) 당연히 시간초과(혹은 스택이 무한적 쌓이므로 메모리 초과)가 난다. 이 문제는 dfs를..

dfs + 백트래킹을 구현만 하면 정답인 문제였고HashSet의 add(), remove(), contains()가 O(1)인것을 이용해 HashSet을 통해 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; public class Main { public static int max = Integer.MIN_VALUE; public static int R ; public static int C ; public static String[][] map; public static HashSet set = n..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net   단순히 모든 node에대해 dfs / bfs를 수행해도 통과할수있는 문제  1) - 단순 bfs + 브루트포스import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int ans;..