IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/2573 "BFS" 전체 맵을 탐색하며 빙산이 있는 곳에 상하좌우를 탐색하여 물이 있는 칸의 개수 만큼 빼주는 것은 쉽다. 이때, 유의해야 할점은 같은 시간대에 앞서 녹아버린 빙하가 0이 되면 이 값이 다른 빙하의 감소에 영향을 끼칠 수 있다는 것이다. 이런 부분을 처리하기 위해 감소 시 0 이 되는 빙하는 바로 감소시키는 것이 아니라 값을 그대로 놔두고, 별도 자료구조에 저장해 놓고, 전체 맵을 다 탐색한 이후에 0 이 되는 빙하들을 처리해 주어야 한다. 해당 풀이에서는 별도의 큐를 두어 관리했다. 더해서 또하나 놓치기 쉬운 조건은 빙하 그룹이 0이 되지 못하는 경우이다. 즉, 한 번에 모든 빙하가 다 녹아버리는 경우이다.이부분은 빙하 ..

출저 : 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/14620 "재귀를 활용한 완전 탐색" 가능한 씨앗의 배치를 모두 검색하는 문제이다. 씨앗을 중심으로 4방향이 화단에 들어오면서, 겹치지 않는 경우에 따라 세 개의 꽃을 배치하고 해당 위치의 가격을 모두 더한 값 중에 최소값이 답이다. 꽃잎 배치의 경우 가장자리에선 꽃을 피지 못하므로 1 ~ N-2 까지 탐색한다. DFS에서 x 좌표를 주어 이전 씨앗부터 탐색한다. (y 좌표도 넣어주면 더 좋지만... N이 크지 않기에 생략) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646..

출저 : https://www.acmicpc.net/problem/11967 "상태 공간에 대한 정확한 이해가 필요" 먼저 상태 공간에 대한 정의가 중요하다. 나는 방문 여부를 체크하는 visited와 해당 방에 불이 켜져있는지를 체크하는 light 두 개의 2차원 배열을 두었다. 그리고 방에 있는 스위치 정보는 x,y 좌표를 x*N +y 를 사용해 index로 변환해서 저장했다. 따라서 아래와 같은 변수를 사용한다. ArrayList[] list; A 방에 도착해서 B 방에 불을 켰고 B까지 갈 수 있다면 가정했을 때, 그 방을 기점으로 해서 다시 탐색을 시작해야함을 주의한다. 나는 처음에 불을 다시 켰을 때 visited 배열을 초기화 시켰는데, 통과는 했으나 시간이 오래 걸려 그냥 q에 넣어주는식으..

출저 : https://www.acmicpc.net/problem/15663 "String을 쓸때도 있다.." 내 블로그 글에... N과 M (1)(https://jaejin89.tistory.com/43) 처럼 char 배열과 더해서 set을 쓰려 했다가, 어라... char 인데.. 2자리면...? 하고 String으로 바꿔서 했다... String 연산은 느리다고 생각해서 String을 안쓰려 했는데 흠... 더 공부해봐야지 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import java.io.BufferedReader;import java.io.IOExcep..

출저 : https://www.acmicpc.net/problem/14226 "BFS, visited 배열을 잘 생각하자.." 해당 문제를 풀다가 visited[] 배열을 어디까지 할까 고민하다.... 1001 로 해서 런타임 에러, 2002 로 했더니 틀렸다.... 잘 생각해보니 특정 이모티콘 길이에 도착했을 때, 버퍼에 1글자를 가지고 오는것과 10글자를 가지고 오는 것은 다른 경우... 따라서 이차원 배열을 방문체크 배열로 해야한다. visited[이모티콘길이][버퍼의길이] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io..

출저 : https://www.acmicpc.net/problem/2839 "BFS를 이용한 탐색" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class Main { static int N; static int min = -1; static int[] visited; static int[] weight = {3,5}; static boolean ok; static Queue q = new LinkedList()..

출저 : https://www.acmicpc.net/problem/15649 "DFS, char[] Array를 사용하자." 순열을 탐색하는 것은 DFS를 통해 쉽다. 그런데 경로를 찍는데 효과적인 방법이 없을까 고민했다. 애초에는 DFS 에 파라미터로 String s 를 하나 더 두어 이를 append 시켜주었지만, N과 M 이 커지면 굉장히 오래 걸릴 것 같았다. String은 immutable 하고, premitive type 도 아니여서 연산이 오래걸린다. 따라서 char[] res 배열을 하나 두어 사용했다. 아주 굳 DFS 탐색 경로를 찍는데 아주 유용할듯 하다. 1234567891011121314151617181920212223242526272829303132333435363738394041..

출저 : https://www.acmicpc.net/problem/8911 "시뮬레이션" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int T; static int d,x,y; static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; static int maxX,minX,maxY,minY; public sta..