문제https://www.acmicpc.net/problem/2638 풀이단순한 BFS 문제이다. 문제의 조건에 보면 가장자리에는 치즈가 항상 없다고 표시된다.BFS를 "치즈가 없는 가장자리" 에서 시작하면 치즈안의 빈 공간은 탐색을 안하면서, 겉에 있는 치즈를 카운트 할 수 있다. 그렇게 바깥쪽에서 탐색을 하다가 이동시에 치즈이면 해당하는 치즈 방문 카운트를 증가시켜준다. 그렇게 BFS 탐색이 한 번 끝나면, 각 치즈의 방문 카운트를 체크해서 2 이상이면 지워주면 된다. 이 과정을 치즈가 모두 없어질때까지 수행하면 해결! 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;// 2변 이상에 닿은 치즈 ->..

문제https://www.acmicpc.net/problem/1238 풀이다익스트라 문제이다. 단순히 n개 각각 마을에서 x 마을로의 최단 거리를 다익스트라로 구하고,그리고 x 마을에서 n개의 마을로의 최단거리를 다익스트라로 구해도 풀리긴한다. x마을에서 n개 마을로의 거리는 한번만에 다 구할 수 있으나,n개의 마을에서 x 최단거리를 구하기 위해서는 n + 1 번의 다익스트라를 돌아야하기에 굉장히 비효율적이다. 해결법은 간선의 방향을 반대로 하고 다익스트라를 수행하면 n 개의 마을에서 x 로 가는 가중치를 한번에 구할 수 있다.n개 각각 마을에서 x로 향하는 길들을 반대로 설정하고 x에서의 다익스트라를 수행하면,그건 각 마을에서 x로 향하는 최단거리가 된다. 이렇게 하면 단 두번의 다익스트라로 문제를 풀..

문제https://www.acmicpc.net/problem/1516  풀이 위상정렬을 활용해 풀어야 하는 문제이다. 처음엔 위상정렬 문제인지 모르고 막 풀었다가.. 호되게 당했다. 사실 위상정렬을 공부하고 나면, 선후관계가 있는 이 문제를 어떻게 풀어야하는지 감이온다. 단지 여기서 가장 큰 문제는, 동시에 건물을 지을 수 있다는 점이다. A와 B건물은 선행 건물이 없고, C 건물은 선행건물로 A B 건물이 있다고 하자. A와 B는 동시에 건설이 시작될테고 더 오래걸리는 20 이 소요되고, 그 때 C를 건설할 수 있을것이다. 이런 부분을 고려해야하는데 A와 B는 같은 수준의 레벨이라고 했을때 C 입장에서 더 오래걸리는 시간을 택해야 한다. 식을 만들어보면 [다음 건물 총 건축시간] = Max(다음건물 총..

문제https://www.acmicpc.net/problem/1283 풀이우선 단축키의 등록 여부를 확인하기 위한 캐릭터 Set을 하나 준비한다. 이후 입력을 받으면 공백을 기준으로 String 을 분리하여 String 배열을 만든다. 우선 나뉜 단어의 첫번째 문자가 단축키가 되는지 확인하기 위해 문자열 반복문을 돌며 첫번째 단어가 Set에 추가되어있는지 확인한다. 이 때 대소문자를 구분하지 않는다고 했기에 uppercase 나 lowercase 로 통일하여 검사한다. 만약 첫단어가 추가되지 않은 단축키면 [ ] 괄호를 추가하여 해당 문자열을 업데이트 하고, 출력시켜준다. 첫단어가 추가되지 않았다면 2중 반복문을 돌면서 추가되지 않은 단축키를 찾으면 된다. 코드import java.util.*;impor..

문제https://www.acmicpc.net/problem/18405 풀이아주 조금의 응용이 들어간 bfs 문제였다. 우선 바이러스가 존재하는 위치를 queue에 저장했다. 단, 바이러스가 여러종류가 있기 때문에 map 을 활용해서 key로 바이러스 번호를 설정하고 그 값으로 해당 바이러스 위치를 가지고 있는 queue 를 꺼내올 수 있도록 설정했다. 이후에는 bfs 를 수행하는데, 이 때 전염이 1회 된다는 점을 주의해야한다. 가장 최근에 전염된 바이러스만 자신 주변으로 감염을 시키기 때문에 queue에는 최근 전염된 바이러스들의 위치만 존재해야하고, 다음에 queue를 넣을때도 마찬가지여야 한다. 숫자가 낮은 바이러스부터 전염되기 때문에 작은 숫자의 바이러스의 queue 부터 접근했고,해당 queu..

문제https://www.acmicpc.net/problem/2239  풀이dfs 를 활용하여 푸는 문제이다. 배열의 앞쪽에서부터 작은값을 하나씩 대입해보고, 해당 값이 스도쿠 조건에 맞는지 검사하는 식으로 풀이가 가능하다. 정답이 여러개일경우 사전순으로 출력하라하였기에, 작은 값을 우선적으로 넣어주는 방식으로 풀이했다. 우선 값을 입력받고, 이 때 0의 개수를 체크했다. 추후에 0의 개수가 0개가 된다면 정답을 발견한것으로 판단하기 위한 용도이다. 이후 2중 for문으로 0 값이 있는 위치를 찾은다음, 해당 위치에 1부터 값을 넣어본다. 선정한 값이 가능한지 여부를 확인하고 (가로, 세로, 3*3 공간) 가능하다면 [1] 배열에 값을 세팅해주고,  [2] 0의 개수를 줄여주고 dfs로 다음 위치를 찾아..

문제https://www.acmicpc.net/problem/22251 풀이설명이 괜히 어렵게 되어있는거 같은데 대충 정리하면 n자리수의 층을 가진 엘레베이터가 있고 최대층과 현재층이 주어질 때, 현재층에서 다른 층으로 갈 수 있는 방법을 구하는 것이다. 이 때 반전이라는 개념을 사용하고, 그 횟수의 제한을 둔다. 우선 각 수를 배열로 나타내었다. 꺼져있는 부분은 0, 켜져있는 부분은 1로 나타냈고그 이후에는 숫자 변형시 필요 반전 개수를 map 에 저장해뒀다.Map> 형태로 구현하였으며cnt = map.get(1).get(3) 라고 했을때 이는 1에서 3으로 바꿀때 필요 반전 개수가 cnt 개라는 뜻이다. 이렇게 구현한 다음 현재층에서 다른 층으로 이동할 수 있는지를 알아봐야 하는데,최대층이 정해져있기..

문제https://www.acmicpc.net/problem/5397 풀이커서를 이동하고, 중간에 값을 삽입하고, 삭제하고 하는 등의 요건을 살펴보면 이 문제가 연결리스트 문제라는걸 알 수 있다. 구현은 단순하다, LinkedList와 ListIterator 를 선언하고 입력받은 값을 순회하면서 로직을 처리한다. "" 또한 마찬가지이다. "-" 가 나올경우에, 가장 앞을 가리키고 있는지 확인하고 (커서가 가장 앞) , 그게 아니라면 연결리스트에서 값을 삭제하고, iterator 를 한 칸 앞으로 이동시켜준다. 그 외에 일반 문자열은 현재 iterator 가 가리키고 있는 위치에 넣어주면 된다. 코드import java.util.*;import java.io.*;public class Main { p..

문제https://www.acmicpc.net/problem/3055 풀이두 스텝으로 진행하면 된다. 1. 물을 먼저 퍼트린다. 2. 고슴도치가 이동할 수 있는 칸을 보고 이동처리를 한다. ※ 물 퍼트리기 우선 물 퍼트리는건, "*" 기준으로 상하좌우로 범위안에 들면서, 빈칸이어야 한다. (".")이 경우에, 임시 배열을 만들어서 새롭게 퍼지는 칸을 체크하고,마지막에 한번에 원본 배열에 물 값을 세팅해주면 된다. ※ 고슴도치 이동 처리 이거는 bfs 로 하면 되는데, 중요한게 있다.한 단계마다 고슴도치가 이동 할 수 있는 걸 모두 체크해야하기에,bfs 수행시 queue 에 들어가 있는, 같은 스텝의 데이터들을 모두 꺼내서 bfs 를 수행해야한다. 일반적으로는 bfs 는 queue에 있는값을 하나씩 꺼내면..

문제https://www.acmicpc.net/problem/2295 풀이알고보면 참 단순한 문제다. 우리는 x + y + z = k 라는 공식을 활용해서 답을 찾아야 하는데, 이 표현은 x + y = k - z 로도 나타낼 수 있다는 점을 알아야 한다. x + y + z 의 경우의 수를 모두 구할려면 O(N^3) 이 걸릴 테지만  이를 조금 비틀어  x + y = k - z  를 활용하면 양쪽의 식들 값을 구하기 위해서 O(N^2) 의 시간에 풀이할 수 있다. x + y 의 값들을 set 에 저장한다음, k - z 값이 set에 있는지 확인하면 된다. 이 때 k 값이 가장 큰 값을 찾고 있기 때문에 배열을 오름차순으로 정렬해준다음,가장 뒤에서부터 k 값을 세팅해서 탐색을 시작하면 된다. k 값을 큰 값..