good_da22

백준 7569번 토마토 (JAVA) 문제 난이도 골드 5 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 풀이 3차원 배열을 사용한 너비 우선 탐색 자바에서 3차원 배열 사용시 면, 행, 열 사용에 주의 너비 우선 탐색을 통해 현재 익은 토마토로 주변 토마토의 영향을 파악 익지 않은 토마토의 전체 개수를 초기에 구한 후 탐색이 돌때마다 이를 최신화한다. 코드 public class Main { static int M, N, H, need, answer; static int[][][] box; static Queue que = new ArrayDeque(); static int[] dDep = {-1, 1}; static int[] dRow = {-1, 1, 0, 0}; static int[] dC..

백준 14502번 연구소 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 풀이 주어진 빈 공간(상태가 0 인 공간) 중 3곳을 선택해서 벽을 설치한다. 벽을 설치한 후 바이러스를 인접한 상하좌우 공간으로 확산한다. 확산이 끝난 후 남은 빈 공간을 계산 코드 import java.io.*; import java.util.*; public class Main { static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; static int N, M, answer; static int[][] map, test; static List space, virus; static boolean[][] ..

백준 14500번 테트로미노 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 브루트포스 알고리즘 풀이 테트로미노의 크기는 4 각 위치에서 4방 탐색으로 갈 수 있는 모든 위치를 4번 탐색하는 것은 모든 테트로미노의 경우의 수(대칭, 회전)을 탐색하는 것과 같다. ㅗ, ㅏ, ㅜ, ㅓ 모양의 경우 한 방향으로 이어지지 않는다. 따라서 2번 때 탐색 시점에서 뻗어가는 경우를 계산한다. 코드 import java.io.*; import java.util.*; public class Main { static int N, M, answer; static int[][] arr; static boolean[][] visited; static int[] dx = { -1, 1, 0, 0 }; static int[]..

백준 2239번 스도쿠 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 백트래킹 풀이 0인 경우, 숫자 1 ~ 9까지 대입 1 ~ 9 까지의 숫자중 스도쿠의 조건을 만족하는 경우(3*3, 행, 열) 해당 위치에 숫자를 대입하고 다음 단계 탐색(방문) 방문 여부를 초기화(0으로) 한 후 대입 가능한 숫자를 계속 탐색 81자리 까지 끝까지 탐색한 경우, 최초의 정답을 반환해야한다.(사전순) 처음 탐색 종료 조건(81자리 모두 탐색)을 만족하면 각 단계를 탐색하기 전에 최최 탐색 완료 여부를 확인 코드 import java.io.*; public class Main { static int arr[][]; static boolean check; public static void main(String[] a..

백준 17471번 게리맨더링 (JAVA) 문제 난이도 골드 4 알고리즘 분류 브루트포스 알고리즘 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 조합론 풀이 N개의 구역 중, 1 ~ N / 2 개의 구역을 선택 N / 2 ~ N -1 개의 구역은 앞서 선택된 구역에서 선택되지 않는 경우로 따로 계산할 필요가 없다. 분리한 구역 내에서 각 그룹이 서로 연결되어 있는지 확인, 너비 우선 탐색 두 그룹 모두 각각 연결되어 있다면, 각 그룹의 인구 수를 계산 코드 import java.io.*; import java.util.*; public class Main { static int N, answer; static List adj; static int[] size; static int[] numbers; publ..

백준 16234번 인구 이동 (JAVA) 문제 난이도 골드 5 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 풀이 너비 우선 탐색을 통해 전체 데이터내에서 연합의 여부를 확인 연합이 발생하는 경우, 다음 단계로 이동 연합이 발생하지 않는 경우, 종료 각 단계 내에서 너비 우선 탐색을 진행, 각 연합 내에서 새로운 인구 수 계산 단계가 끝나고 방문여부 초기화 코드 import java.io.*; import java.util.*; public class Main { static int N, L, R; static int[][] map; static int[] dx = { -1, 0, 1, 0 }; // 상, 우, 하, 좌 static int[] dy = { 0, 1, 0, -1 }..

백준 14889번 스타트와 링크(JAVA) 문제 난이도 실버 2 알고리즘 분류 브루트포스 알고리즘 백트래킹 풀이 N명 중 N/2 명을 선택하여 능력치 합을 구하고 선택되지 않은 N/2명 의 능력치 합을 구한다. N 명 중 N/2 명을 뽑는 조합 6명 중 1, 2, 3을 뽑는 것은 4, 5, 6을 뽑는 것과 같다. N/2를 뽑는 조합을 절반만 수행할 수 있다. 1 ~ N 까지의 수 중 N / 2개를 선택하는 과정에서 1을 포함하는 경우와 1을 포함하지 않는 경우로 나눌 수 있다. 1을 포함하는 N / 2개를 선택하고 선택되지 않는 경우와 비교 코드 public class Main { static int N; static int[][] arr; static int answer; static int[] num..

백준 21578번 꿀 따기 (JAVA) 문제 난이도 골드 5 알고리즘 분류 그리디 알고리즘 누적 합 많은 조건 분기 풀이 누적 합을 이용하기 위해 입력 시 누적된 합을 계산한다. 이후 중간에 벌통이 위치한 경우에서 사용하기 위해 입력 값 중 최댓값을 찾는다. (양쪽 끝 위치 제외) 벌통의 위치 왼쪽 끝에 있는 경우 오른쪽 끝에 있는 경우 중간에 있는 경우 왼쪽 끝에 있는 경우 한 마리 벌은 오른쪽 끝에 위치 (누적 합을 최대로 만들기 위해) 나머지 한 마리는 오른쪽 벌과 왼쪽 끝에 위치한 벌통 사이에 위치 오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 0 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값) 중간에 위치한 벌이 따는 꿀의 합 = (현재위치 - 1 ~ 0 까지의합) 오른쪽 끝에 있..

백준 13975번 파일 합치기3 (JAVA) 문제 난이도 골드 4 알고리즘 분류 자료구조 그리디 알고리즘 우선순위 큐 풀이 모든 파일이 합쳐지는 동안 최초 두 파일을 합치는 경우의 비용은 누적된다. 누적되는 비용의 최소화 필요 가장 작은 비용의 두 파일을 합치고 하나의 파일로 연산한다. 코드 public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); Strin..

백준 17204번 죽음의 게임 (JAVA) 문제 난이도 실버 3 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 풀이 출발번호(0) 부터 목표번호(K)로 가는 최솟값 구하기 어떤 방법으로도 K로 갈 수 없는 경우는 K에 도착하기 전에 사이클이 발생한다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); StringBuilder sb =..