출저 : https://www.acmicpc.net/problem/2026 "DFS 문제를 잘 읽어야함..." 문제를 잘 안 읽어서 계속 틀렸음. 문제를 잘 읽어 보면 선택된 K명의 모든 애들이 다 친구여야 함. 최초에 1-3-2-4 의 관계가 되면 나는 1,2,3,4 모두 답으로 출력했음. 이거 빼고는 그냥 DFS 문제. 따라서 아래 68~ 73 라인을 추가했음. 팁으로 경로를 찍을 때는 list 보다는 아래와 같이 result 배열 하나만을 생성해 이를 이용해 경로를 찍는 것이 더 좋다고 생각됨. 또 하나, 전부 친구인지 아닌지 판별하는 부분에서 boolean 변수를 사용할 수도 있지만 이미 생성된 j를 가지고 끝까지 돌았는지 j == index 인지 판별하면 변수 생성을 하나 줄일수 있으미.. 12..
출저 : https://www.acmicpc.net/problem/1389 "다익스트라,BFS,DFS 다~~" 다익스트라를 연습할 수 있는 좋은 문제 인 듯, 일단 다익스트라는 BFS를 활용해 시작지점으로부터 연결된 모든 노드로 가는 최소값을 찾는 알고리즘이다. ( 단, 다익스트라는 가중치가 각각 다른 경우에 유용하며, 이 문제에서는 가중치가 1이므로 그냥 BFS 혹은 DFS 탐색하면됨...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869import java.io.BufferedReader;import java.io.IO..
출저 : https://www.acmicpc.net/problem/2309 "DFS" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.util.Arrays;import java.util.Scanner; public class Main { static int[] talls = new int[9]; static boolean[] visited = new boolean[9]; static boolean find; static int[] res = new int[7]; static Scanner sc = new Scanner(System.in); public static v..
출저 : https://www.acmicpc.net/problem/14889 "비트마스크도 쓸수 있고, 그냥 DFS 로 짝지어서 할 수도 있고" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; class Main { static int N; static int[][] map; static bo..
출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB "무식한 DFS" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;import java.util.StringTokenizer;p..
출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx "DFS와 가지치기" DFS를 이용해 해당 위치의 명령을 수행한다. 이 때, '?' 명령의 경우 4방향 dx,dy 에 대해 모두 탐색해 준다. 가능한 경우가 나왔을 때는 boolean 변수 find를 true 설정해주어 더이상 탐색하지 않도록 한다. 범위가 벗어날 경우 문제에서 제시한 예외처리를 해주는 것도 중요하다. 일일이 x,y 좌표가 범위를 벗어난 경우를 체크하자. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474..
출저 : https://www.acmicpc.net/problem/1325 "아직도 모르겠는 문제...ㅎㅎ" 나는 처음에 해당 문제를 DFS DP를 이용해서 풀었다. 아래와 같이... 근데 시간초과가 나더라... ㅎㅎ 생각의 전환이 필요했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.ut..
출저 : https://www.acmicpc.net/problem/3967 "DFS 백트래킹" 시간초과로 삽집을 좀 했던 문제.. 알파벳 원소들의 위치를 p 에 저장해 두고, 조합을 만들고 나중에 이 좌표 정보를 가지고 valid 체크를 하였다. (이 p 배열을 그냥 풀어서 쓰면 시간이 많이 줄여진다.....) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586import java.io.BufferedReader;import java.io.IOException;imp..
출저 : https://www.acmicpc.net/problem/1799 "독립사건을 분할처리해서 시간복잡도를 줄인다." N-queen 과 유사하게 해당 문제를 풀려고 시도했고, 생각보다 금방 풀리네? 라는 생각을 했다. 하지만 시간 초과... 시간복잡도를 줄여야 한다. 중복 탐색하는 부분은 없었고 어딘가 시간 복잡도를 줄일 방법을 찾아야 했다. 원래 시간복자도는 O(2^(N*N)) 로 제한 시간내에 문제를 풀 수가 없다. 비숍의 움직임 특성을 보면 4방향 대각선으로만 영향을 끼친다. 즉 아래 체스판을 봤을 때, 같은 색깔의 칸에만 영향을 미친다. 검은칸에 비숍들과 흰 칸의 비숍들은 독립적인 사건인 것이다. 따라서 전체 탐색 범위를 줄여 시간복잡도를 줄이는 방법을 쓴다. O(2^N) 이 될 것 같다. ..
출저 : https://www.acmicpc.net/problem/11967 "상태 공간에 대한 정확한 이해가 필요" 먼저 상태 공간에 대한 정의가 중요하다. 나는 방문 여부를 체크하는 visited와 해당 방에 불이 켜져있는지를 체크하는 light 두 개의 2차원 배열을 두었다. 그리고 방에 있는 스위치 정보는 x,y 좌표를 x*N +y 를 사용해 index로 변환해서 저장했다. 따라서 아래와 같은 변수를 사용한다. ArrayList[] list; A 방에 도착해서 B 방에 불을 켰고 B까지 갈 수 있다면 가정했을 때, 그 방을 기점으로 해서 다시 탐색을 시작해야함을 주의한다. 나는 처음에 불을 다시 켰을 때 visited 배열을 초기화 시켰는데, 통과는 했으나 시간이 오래 걸려 그냥 q에 넣어주는식으..
- Total
- Today
- Yesterday