CODING/BAEKJOON72 [BAEKJOON] 치즈 원래 치즈 모양과 예제 입력에서 치즈 내부의 구멍이 있는 '0'인 곳은 공기로 보면 안 된다. 치즈가 아닐 뿐 외부 공기와 맞닿아 있지 않았기 때문이다. 또한, 예제 입력에서 판의 가장자리에는 치즈가 놓여있지 않다고 하니 외부 공기로 판단하여 bfs 혹은 dfs로 가장 겉부분의 치즈만 파악할 수 있다면 모든 치즈가 녹는 데까지 시간을 구할 수 있을 것이다. 시간이 1씩 증가할 때마다 공기의 상, 하, 좌, 우 방향으로 겉부분의 치즈를 공기에 노출되게끔 한다. 모든 치즈가 사라지기 전의 시간을 출력해야하므로 매 시간이 흐를 때마다 먼저 치즈의 전체 개수를 세고, 외부 공기를 맞닿게 하는 순서로 진행한다. [BFS 풀이] import java.io.BufferedReader; import java.io.IO.. 2022. 10. 23. [BAEKJOON] 직사각형 쿼리 2차원 배열에서 자연수 1부터 10까지 카운트 할 수 있도록 3차원 배열로 확장하여 누적합 풀이를 적용한다. arr[x][y][k]는 x행, y열까지 자연수 k가 몇 개까지 카운트되었는지를 담고 있다. x1, y1부터 x2, y2까지 자연수 k의 누적 개수는 arr[x2][y2][k] - arr[x2][y1-1][k] - arr[x1-1][y2][k] + arr[x1-1][y1-1][k] 이다 그 이유는 아래 그림으로 설명 가능하겠다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamW.. 2022. 9. 22. [BAEKJOON] 아기상어 ※ 아기상어가 먹을 수 있는 물고기를 찾는다고 해서 바로 먹으면 금물! 먹을 수 있는 물고기 리스트에 저장해놨다가 가장 위에 있는, 그 다음으로 가장 왼쪽에 있는 물고기 딱 한 마리만 먹을 수 있다는 것을 잊지 말자. 이때 활용한 것이 Comparable 인터페이스이다. 아기상어와 물고기의 거리를 나타낼 dist 필드를 기준으로 정렬해줄 건데, 아래 코드를 보면 거리가 같을 경우, 가장 위쪽(x 좌표가 더 작은)에 있는 물고기로, 물고기 위치를 상하로 따질 수 없는 경우는 최후의 수단으로 가장 왼쪽(y좌표가 더 작은)에 있는 물고기를 선택할 수 있도록 compareTo() 메소드가 정의되어 있다. ✅ 반복, 종료조건 파악하기 초기 위치에서 가장 가까이에 있는 위치의 물고기를 찾아나선다(bfs). 가장 가.. 2022. 8. 30. [BAEKJOON] 스위치 켜고 끄기 학생수만큼 받은 번호에 따라 스위치 처리 남학생일 경우 : 받은 번호의 배수인 스위치 모두 변경 (0 → 1 , 1 → 0) 여학생일 경우 : 받은 번호를 중심으로 상태가 대칭되는 스위치 모두 변경 (0 → 1 , 1 → 0) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BaekJoon1244 { static int N, student; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader .. 2022. 8. 2. [BAEKJOON] 연구소 0 - 안전 지역 1 - 벽 2 - 바이러스 우리의 목표는 3개의 벽을 세워 최대한 바이러스가 퍼지지 않게 해야 한다. 먼저 벽을 세울 수 있는 안전 지역 3 곳을 '조합' 하자. 조합이 이루어졌을 때마다 바이러스가 모두 퍼졌다 가정하고, 남은 안전 지역의 수를 세어 최댓값을 반환하면 된다. 문제 풀이 팁 1. 연구소 초기 상태를 입력 받아 저장할 때 바이러스의 위치, 안전 지역 위치를 각각의 리스트에 담는다. → 벽을 세울 위치 3 곳을 조합할 때 안전 지역(0)인지 확인하는 조건문 없어도 됨! 리스트에 담긴 위치에서만 3곳 조합하면 됨 2. 벽을 세울 위치 3곳을 조합했을 때의 연구소 상태에서 바이러스를 퍼뜨려본다. 그리고 남은 안전 지역 수를 센다. 안전 지역 수의 최댓값을 갱신한다. 1️⃣ 벽을 .. 2022. 7. 21. [BAEKJOON] 2468번 안전 영역 높이가 1인 지역부터 최대 높이까지 잠기지 않는 안전 영역의 최대 갯수를 구하는 문제이다. 잠기지 않는 영역은 어떻게 구할까? 전체 구역을 돌면서 잠기지 않는 영역의 지점을 찾으면 BFS/DFS로 해당 지역을 방문처리 하면 된다. 1. 높이가 1일 때부터 최대 높이까지 반복 2. 전체 구역을 돌면서 안전 구역을 발견하면 BFS 탐색 시작 3. 해당 높이에서의 BFS 호출 횟수만큼 cnt++ 4. 해당 높이에서의 탐색 종료되면 최대 cnt 값 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; .. 2022. 5. 26. 이전 1 2 3 4 5 6 ··· 12 다음
