알고리즘/백준
-
[백준] 16973. 직사각형 탈출 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 16973번: 직사각형 탈출 https://www.acmicpc.net/problem/16973 💡 문제 분석 직사각형의 가장 왼쪽 위칸(Sr, Sc)를 기준으로 4방향으로 BFS를 진행합니다. 4방향을 탐색할 때, H * W 크기의 직사각형 중 한칸이라도 벽에 부딪힌다면 continue. (Fr, Fc) 좌표를 찾아낸다면 종료합니다. ⌨️ 코드 import java.io.*; import java.util.*; public class Q16973 { static int N, M, H, W, sy, sx, fy, fx; static int[][] map, dist; static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; public static vo..
-
[백준] 16234. 인구 이동 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크16234번: 인구 이동N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.https://www.acmicpc.net/problem/16234 💡 문제 분석N * N크기의 땅을 순회하면서, 4방향으로 인접해있는 나라에 인구 차이가 L명 이상 R명 이하라면 연결되는 양방향 그래프를 만든다.그래프를 만들고, 모든 땅을 순회하면서 그..
-
[백준]15686. 치킨 배달 (Java)알고리즘/백준 2021. 9. 4. 15:14
💡 문제 분석/** * 0은 빈 칸, 1은 집, 2는 치킨집 * 치킨 거리가 최소가 되게 치킨집을 M개 뽑고 나머지는 폐업 * 원래 있던 치킨집들을 배열에 저장하고, 그 중 M개를 뽑는다. * 뽑은 M개를 가지고 모든 집을 돌며 최소 치킨 거리를 구한다. */ ⌨️ 코드JAVAimport java.util.*; public class Q15686 { static int n, m, ans = (int)1e9; static List home, chicken; static int[] pick; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); home = n..
-
[백준]15683. 감시 (Java)알고리즘/백준 2021. 9. 3. 15:04
💡 문제 분석/** * 1. 전체 사무실을 순회하면서 CCTV가 나오면, CCTV의 번호에 맞는 방향으로 감시 영역을 표시한다, 감시 영역의 방향은 종류에 따라 4가지, 2가지, 1가지가 된다 * 2. 모든 CCTV의 감시 영역 표시가 끝나면 사각지대의 영역을 카운트한다. */ ⌨️ 코드JAVAimport java.io.*; import java.util.*; public class Q15683 { static int N, M, ret = Integer.MAX_VALUE; static int[][] map; static ArrayList al = new ArrayList(); static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; static int u = 1, r..
-
[백준]15591. MooTube (Java)알고리즘/백준 2021. 9. 3. 15:04
💡 문제 분석/** * 1. N개의 정점에 N - 1개의 동영상 쌍이 있기 때문에, 트리 모양, 모든 정점으로 갈 수 있다. * 2. 탐색을 진행하며, 유사도가 K보다 작은 경우가 나오면, 그 이후는 어차피 K보다 작은 유사도이기 때문에 탐색을 멈춘다 */ ⌨️ 코드JAVAimport java.io.*; import java.util.*; public class Q15591 { static int N, Q; static List[] adj; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); Q = sc.nextInt(); adj = new ArrayList[N + 1]; for(int..
-
[백준]14891. 톱니바퀴 (Java)알고리즘/백준 2021. 9. 3. 15:04
💡 문제 분석/** * 1. 연결리스트를 이용해서 톱니가 회전하는 것을 구현합니다. * 2. 톱니바퀴를 회전시킬 때, 양 옆의 극을 확인하고 회전할지 말지 결정합니다 */ ⌨️ 코드JAVAimport java.util.*; public class Q14891 { static int K; static LinkedList[] wheel = new LinkedList[4]; static boolean[] chk; public static void main(String[] args) { Scanner sc = new Scanner(System.in); for(int i = 0; i < 4; i++) wheel[i] = new LinkedList(); for(int i = 0; i < 4; i++) { Strin..
-
[백준]14719. 빗물 (Java)알고리즘/백준 2021. 9. 3. 15:04
💡 문제 분석/** * 1. 0부터 W까지 옆으로 이동하면서, 현재 자신의 칸을 기준으로 좌우로 나눕니다 * 2. 왼쪽 부분에서 가장 높은 부분과, 오른쪽 부분에서 가장 높은 부분 사이에 빗물이 고이기 때문에 * 양 옆중 낮은 부분과 현재 자신의 높이의 차이만큼 빗물이 고이게 됩니다. */ ⌨️ 코드JAVAimport java.io.*; import java.util.*; import java.util.stream.IntStream; public class Q14719 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); sc.nextInt(); int w = sc.nextInt(); List map = new Ar..
-
[백준]14503. 로봇 청소기 (Java)알고리즘/백준 2021. 9. 3. 15:04
💡 문제 분석/** * 1. 현재 위치를 청소한다. * 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다. * a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. * b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. * c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. * d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. * * 3. 문제에서 요구하는 순서대로 정확하게 구현하자 */ ⌨️ 코드JAVAimport java.io.*..