출저 : https://www.acmicpc.net/problem/2178 "BFS를 활용한 최단거리 탐색" 해당 문제는 BFS를 활용해서 왼쪽 상단에서, 오른쪽 하단까지의 최단거리를 탐색하는 문제이다. BFS 에서 중요한 것은 갈 수 있나 없나를 체크하는 것과 중복 경로를 줄이는 것이다. 아래 풀이에서는 int형 배열 visited를 활용한다. visited 배열에는 해당 지점에 지나온 칸의 개수가 저장된다. 그 전에, 경로 A가 특정 지점 x, y 를 지날 때, 이미 저장된 visited[x][y] 에 값이 자신보다 더 작은 경우라면 경로 A는 더 이상 탐색할 필요가 없다. 이미 자신보다 더 최단 경로로 지나간 경우가 있기 때문에... 이러한 경우들을 생각해서 중복을 줄여준다. 그 외에 우선순위 큐를..
출저 : https://www.acmicpc.net/problem/1260 "DFS와 BFS 기초" 가장 기초적인 DFS와 BFS 탐색 문제이다. DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다. 해당 문제에서는 인접행렬을 가지고 그래프의 연결 상태를 나타내었다. 하지만 노드의 개수가 많아진다면, 제한된 메모리 내에서 인접 행렬을 만들기 제한되기 때문에, 인접리스트를 만들어서 처리할 수도 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667import java.io.BufferedReader;import java.io.I..
출저 : https://www.acmicpc.net/problem/15953 "시뮬레이션" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; class Main { static int T; static int[] c2017 = {500,300,200,50,30,10}; static int[] c2018 = {512,256,128,64,32}; static int[]..
출저 : https://www.acmicpc.net/problem/1107 "브루트 포스의 존재, 순서" 예전에 분명히 풀었던 문제인데 풀질 못했다. 반성해야겠다. 해당 문제는 브루트 포스 즉, "다해보기" 문제이다. 재귀적으로 가능한 경우의 수를 모두 검색한다. 그렇다면, 언제 까지 재귀를 돌릴 것인가? 즉, 기저사례가 언제 일까? 나는 현재 입력으로 들어온 채널의 길이 +1 까지를 기저사례로 정했다. 번호를 눌러서 갈 수 있는 채널들로부터 목적지 채널까지 거리를 비교해줬다. (처음에는 번호를 누르는 것과 동일하게 +,- 버튼도 함께 돌려 버려서 이상한 결과가 나왔다.. 51 > (-) > 50 > 0 > 500 이런 식으로...) 아무튼... 버튼을 누르고, 해당 위치에서 목적지 채널까지 거리를 비교..
출저 : https://www.acmicpc.net/problem/3006 "세그먼트 트리...?" 문제를 풀고나서 시간이 오래 걸려 찾아 보았더니 이 문제는 세그먼트 트리를 이용해서 풀어야 한다고한다. 하지만, 허접인 안는 세그먼트 트리가 뭔지 몰랐고, 생짜 구현했다. 세그 먼트 트리에 대해서 공부한 후에 다시 풀어봐야 겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475import java.io.BufferedReader;import java.io.IOException;import java.io...
출저 : https://www.acmicpc.net/problem/6087 "BFS는 갈수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요." 거울 설치(https://www.acmicpc.net/problem/2151) 와 같은 문제이다. 다른 조건을 최소화하는 경우를 구할 때는, 다익스트라 혹은 우선순위 큐를 사용한다. 더해서 BFS는 항상 갈 수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899..
출저 : https://www.acmicpc.net/problem/1347 "시뮬레이션" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays; class Main { static int N; static char[][] map = new char[250][250]; static int maxX; static int maxY; static int ..
출저 : https://www.acmicpc.net/problem/2980 "시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; class Main { static int N,L; static int[] map; static Node[] nodes; static int cur, time; public static void main..
출저 : https://www.acmicpc.net/problem/3985 "시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; class Main { static int L,N; static int[] map; static int[][] dist; static int max1,max2,idx1,idx2; public static void main (String[] arg..
출저 : https://www.acmicpc.net/problem/3197 "이분탐색, 맵 재정의" 문제는 이분 탐색을 통해서도 풀 수 있고, 우선순위 큐를 통해서도 풀 수 있다. 더 나아가.. union find ? 를 통해서도 풀 수 있다는데 잘 모르 겠다. 이번 풀이에서는 우선순위 큐를 사용해서 풀도록 한다. 사실 더 좋은 풀이가... 있는 것 같긴 하다 ㅠ 메모리 소요와 시간 초과가 너무 크다. 몇일 고생하다가 푼 문제라... 어쨌든 풀리긴 풀려서 다행. 그럼 풀이를 하면 가장 먼저 맵을 재정의 해야 한다. char[][] map 이외에 int[][] 형 맵을 별도로 두어 각 빙판이 몇일 째에 사라지는지를 마킹 한다. 그렇게 한 후, 이분 탐색을 한다면 빙판을 다 녹여보아서 end 값을 구하고, ..
- Total
- Today
- Yesterday