IT 개발 돼지의 일상

출저 : 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..

출저 : https://www.acmicpc.net/problem/6987 "가능한 모든 경기 결과를 탐색해 주어진 결과를 만족하는 경우가 있는지 찾자" 처음 이 문제를 너무 단순하게 생각했다. 각 조에서 이루어진 경기 결과 중 승과 패가 같고, 무승부인 경우가 짝수개로 나오는지만 확인하면 되는 줄 알고, 그렇게 해서 애를 먹었다.. 제대로된 접근 방법은 각 조의 6개의 국가가 돌아가면서 모두 한번씩 경기를 치룬다고 했으니 가능한 경기는 아래와 같이 총 15개 이다. A : {B,C,D,E,F}B : {C,D,E,F}C : {D,E,F}D : {E,F}E : {F} 경기의 순서는 상관 없다. 이 15개의 경기에서 매 경기 가능한 결과 (A 가 이기고 B가 지고 , B가 지고 B가 이기고, A 와 B가 무..

출저 : https://www.acmicpc.net/problem/7576 "단순 BFS" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import 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 ..

출저 : https://www.acmicpc.net/problem/1697 "단순 BFS" 수빈이가 이동할 수 있는 방법을 길이 3인 배열로 만들어 처리했음. 12345678910111213141516171819202122232425262728293031323334353637383940414243import 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 int N,K; static int INF = 1000..