우보천리 개발

백준 18310 안테나 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 아이디어 안테나의 위치가 배열의 가운데 있으면 거리가 최소가 되는것을 확인할 수 있다. 즉 배열을 오름차순으로 정렬하고 배열의 가운데 있는 값을 찾으면 된다. 코드 import java.util.*; class BJ18310 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextIn..

백준 10825 국영수 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 아이디어 Comparator 을 재정의해서 문제에서 요구하는 기준으로 정렬을 하면 되는 문제이다 코드 import java.io.*; import java.util.*; class BJ10825 { // 문제에서 요구하는 점수와 이름을 저장하는 클래스를 정의하는데 // 정렬 기준을 정의해야하기 때문에 Comparable 클래스 구현 static clas..

백준 18428 감시 피하기 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 아이디어 백준 14502 연구소 문제와 비슷하게 접근했다 장애물을 3개 설치할 수 있다. 즉 장애물을 빈 곳에 넣으면서 경우의 수를 확인한다 그래프에서 선생님이 있는 곳은 따로 노드에 저장하고 먼저 큐에 넣어준다 큐에서 선생님이 있는 위치마다 상하좌우를 탐색 하고 조건에 따라 "YES" "NO"를 출력해주면 된다 나머지는 코드에서 코드 package baekj..

백준 14888 연산자 끼워넣기 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 아이디어 사칙연산이 순서대로 주어지기 때문에 사칙연산의 개수를 담는 배열을 만든다 이후 사칙연산의 조합을 재귀적으로 호출하여 모든 경우의 수를 확인한다 마지막에 사용한 사칙 연산의 개수를 다시 증가시켜줘야한다 코드 import java.util.*; class BJ14888 { static int[] ma..

백준 14502 연구소 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 아이디어 벽을 3개 세워야하는데 DFS를 통해서 연구소 내에 벽 3개를 세울 수 있는 경우의 수에 대해서 모두 계산한다 벽을 3개 세웠으면 바이러스가 퍼져야하는데, BFS를 통해서 주변에 벽에 없는 곳으로 바이러스가 퍼질 것이다 매번 바이러스가 없는 영역을 구해서 최대값으로 갱신한다 DFS + BFS를 사용해서 풀기 코드 import java.util.*; class BJ1450..

이것이 코딩테스트다 - 미로탈출 P.152 아이디어 최단거리 같은 것을 구하는 것은 BFS 알고리즘으로 탐색해야된다. 이유는 바로 인접 노드부터 탐색하기 때문이다 미로의 좌표를 가는 곳마다 현재 노드 +1로 해주면 탈출구가 있는 (N,M) 에는 (1,1) 에서 출발 후 도달하는 거리가 나온다 코드 import java.util.*; class tct4 { static class Node { int x,y; public Node(int x, int y) { this.x = x; this.y = y; } } static int[][] graph; static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static int n,m; public static v..

이것이 코딩테스트다 - 음료수 얼려먹기 Page 149 아이디어 인접한 칸으로 0이 있는지 확인하며 DFS/BFS 탐색하면 된다 0으로 연결되었으면 한개의 얼음으로 간주하기 때문에 한번도 방문하지 않았고, 0인 경우에만 개수를 세주면 된다 코드 import java.util.*; class tct3 { static class Node { int x,y; public Node(int x, int y) { this.x = x; this.y = y; } } static Queue q = new LinkedList(); static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static int count, n, m; static boolean[][] visit..

백준 18405 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 아이디어 백준 7576 토마토  문제와 비슷하게 큐에 먼저 필요한 개체를 넣어야함 바이러스의 종류가 1~K번이 있는데, 작은 바이러스가 먼저 퍼진다 --> 토마토 문제와 비슷하게 익은 토마토를 먼저 즉, 낮은 번호의 바이러스를 큐에 넣는다. 바이러스의 순서를 정하기 위해서는 바이러스 객체에 x,y 뿐만 아니라 index값과 시간 저장한다..

백준 18405 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 아이디어 백준 7576 토마토  문제와 비슷하게 큐에 먼저 필요한 개체를 넣어야함 바이러스의 종류가 1~K번이 있는데, 작은 바이러스가 먼저 퍼진다 --> 토마토 문제와 비슷하게 익은 토마토를 먼저 즉, 낮은 번호의 바이러스를 큐에 넣는다. 바이러스의 순서를 정하기 위해서는 바이러스 객체에 x,y 뿐만 아니라 index값과 시간 저장한다..

백준 7576 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 BFS로 탐색을 하는데, 익은 토마토와 인접한 곳부터 익어야하기 때문에 큐에 익은 토마토를 미리 다 넣어준다. 2차원 배열로 만들어서 탐색하는데, 1인 곳은 새로 정의한 Tomato 클래스로 미리 큐에 넣는다 그렇게 되면 1과 인접한 곳부터 모두 탐색하는데 0이 아닌곳은 탐색하지 않음 마지막에 배열을 확인해서 익지 않은 토마토가 있는지, 아니면 모두 ..