개발하는 고라니

15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net [DFS] 몇 시간을 고민해보아도 풀지 못해 풀이를 찾아 보던 중, 너무 간단하게 푼 풀이가 있어 많은 것을 깨달았다. 나는 아직 DFS 응용을 하기에는 벅차다는 것을.. 문제의 실마리를 찾을 때 조금 더 집중하고 깊이 들여다보는 습관을 길러야겠다. 다음 풀이는 Sleeping Rabbit님의 블로그를 참고하였다. 리프노드의 높이를 구하고, 각 리프노드들의 높이를 모두 더한 합이 짝수이면 실패, 홀수이면 성공 이라는 간단한 명제로 풀이를 진행하셨는데, 내가 너무 ..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [BFS] 전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이... 각 정점은 0~15를 갖을 수 있는데, 0 : 벽이 없음 1 : 서쪽으로 벽 2 : 북쪽으로 벽 4 : 동쪽으로 벽 8 : 남쪽으로 벽 이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳) #풀이 요약 1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2..

2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net [이진탐색, Binary Search] long타입의 정수 중 제곱했을 때 n보다 큰 값중 가장 작은 값을 찾는 문제. left = 0, right = n으로 세팅하고 이진탐색을 진행하면 쉽게 찾는다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net [DFS] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static StringBuilder sb = new StringBuilder(); static boolean isPrime(int x){ if(x == 1) return false; for(int i=2..

14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net [DFS or BFS] R x C 배열에서 방문하지 않은 각 좌표를 시작으로 1로 연결된 부분의 개수를 찾으면 되는 비교적 간단한 문제이다. 단 대각선도 이동 가능함에 주의하자. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int r, c; static int[][] map = new int[251][251]; static i..

3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net [DFS or BFS] 나는 DFS를 연습할 겸 DFS로 풀었다. R x C의 지도에서 벽으로 둘러쌓인 각 영역내의 늑대와 양의 개수를 찾아 전체 늑대와 양의 개수에 변화를 주었다. 지도를 입력 받을 때 전체 양의 개수와 늑대의 개수를 파악하고, 각 영역을 DFS 돌며 그 영역의 늑대와 양의 개수를 파악해 늑대 >= 양이면 전체 양에서 해당 양만큼 줄이고, 반대면 늑대를 줄인다. # Code import java.io.BufferedReader; i..

10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net [Dijkstra] 이 문제의 정점은 n+2개다. 출발점, 도착점, 그리고 n개의 대포들. 다음과 같은 주의사항을 지닌다. 1) 출발점/도착점은 인간 대포를 사용할 수 없다. 2) 한 정점에서 다른 정점으로 갈 수 있는 방법은 오직 걸음으로만 가거나, (인간 대포 + 걸음)을 이용하는 방법이 있다. (단, 출발점/도착점은 제외) 3) 대포를 사용할 시, 거리가 50 이상일 때와, 50 미만일 때를 고려해야한다. 나는 정점에 대한 클래스와 간선에 대한 클래스..

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net [BFS] 바로 본론부터 얘기하자면, 일반적인 BFS와 다른 점이 존재한다. 바로 각 정점은 방향을 갖는다는 것이다. 여기서 방향이란 상하좌우를 의미한다. 방향이 존재하므로 배열도 3차원이 되어야한다. 예를 들어 방문했는지에 대한 체크하는 배열 visit[ ][ ][4], 각 정점에서 해당 방향으로 도착했을 때의 거울이 몇개 필요했는지에 대한 배열 mir[ ][ ][4]. 이뿐만이 아니다. 레이저와 거울의 특성을 고려해보면, 레이저를 거울에 비추었을 때..