개발하는 고라니

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]. 이뿐만이 아니다. 레이저와 거울의 특성을 고려해보면, 레이저를 거울에 비추었을 때..

13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net [Floyd-Warshall or 다익스트라] 나는 플로이드-와샬로 풀었으나, 다익스트라로 푸는 것이 어쩌면 더 적은 시간이 들지도 모르겠다. 다익스트라를 사용한다면 k번의 다익스트라를 수행하게 되니까 말이다. 일반적인 플로이드 와샬 문제처럼 거리의 대한 배열 dist를 i == j일때는 0으로, 아닐때는 INF로 초기화 해놓고, 입력에 따라 dist에 값을 대입한다. for(int i=1; i