CODING/BAEKJOON72 [BAEKJOON] 효율적인 해킹 풀이 방법 1. a → b 단방향 그래프 생성, 방문 카운트용 int형 answer 일차원 배열 생성 2. 모든 컴퓨터를 시작 지점으로 설정하여 각각의 경로 찾아갈 때마다 visited 배열 초기화 3. 해킹 가능한 컴퓨터 순회 돌면서 방문하지 않았다면 bfs 탐색 4. bfs 내부에서 해킹 가능한 컴퓨터를 만났다면 현재 컴퓨터 번호(=index)에 +1 5. 한 번에 해킹 가능한 최댓값을 찾아서 최댓값과 카운트가 같은 컴퓨터 번호 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; impor.. 2023. 8. 10. [BAEKJOON] 플로이드 하나의 출발점에 대해 모든 정점의 최단 경로를 구한 다음, 문제에서 요구하는 도착점까지의 최단 경로를 출력한다. 다익스트라 알고리즘으로 풀이 1. 모든 정점의 비용을 최댓값으로 초기화한다. (시작점의 비용은 0) 2. 최단 경로여야 하므로 우선순위큐를 사용하여 비용이 오름차순 정렬되게끔 한다. (작은 비용의 경로먼저 탐색) 3. 탐색해야 할 노드의 비용이 현재까지 지나온 비용보다 클 경우는 탐색할 필요 없음 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Prior.. 2023. 8. 2. [BAEKJOON] 치즈 1. 외부 공기 (0, 0)부터 시작이라 가정하여 bfs 돌리기 2. 공기와 맞닿은 치즈는 맞닿은 횟수만큼 카운트 하기 3. 공기와 맞닿은 부분이 2회 이상이라면 녹은 치즈로 판단하기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N, M, total; static boolean[][] cheese; static int[][] arr, dir= {{0,1},{0,-1},{1,0}.. 2023. 7. 21. [BAEKJOON] 녹색 옷 입은 애가 젤다지? SWEA의 '등산로 조정' 문제와 유사하다고 느껴졌다. 1. [0][0]칸에서 시작해 [N-1][N-1] 칸까지 최소 비용으로 도달할 수 있는 완전 탐색을 한다. 2. BFS를 사용했으며 우선순위큐로 현재 비용이 더 작은 것부터 탐색한다. 3. 현재 비용이 더 작은 것은 어떻게 알 수 있는가 ? 4. visit 방문 체크를 하지 않고, 초기 값을 Integer.MAX_VALUE 값으로 설정해주어 현재까지의 비용과 비교하며 더 작은 값으로 갱신한다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Output.. 2023. 2. 25. [BAEKJOON] 색종이 만들기 분할 정복 방법으로 접근해야 하는 문제이다. 흰색과 파란색 정사각형 색종이의 개수를 각각 알아내어야 하는데 만약 1/2씩 접었을 때 나뉘어진 영역을 모두 같은 색상이어야 더 이상 나뉘지 않음을 알 수 있다. 만약 나뉜 영역이 오로지 한 색상만을 가지고 있지 않다면 다시 1/2씩 접혔다는 것을 의미한다. 아래 이미지와 같이 전체 붉은 영역이 한 색상만을 가지고 있지 않으므로 4등분으로 분할하고, 나뉜 부분 색종이를 하나씩 떼어 보았을 때에도 한 색상만을 가지고 있지 않다면 4등분, 한 색상을 유지한다면 현재 색상의 카운트를 증가시켜 return한다. 이렇게 반복하다보면 흰색, 파란색의 색종이의 개수를 카운트 하며, 모두 같은 색상인 가장 작은 단위의 색종이를 마지막으로 return될 것이다. import .. 2022. 12. 23. [BAEKJOON] 낚시왕 이 문제는 크게 두 가지 스킬만 깨우친다면 쉽게 풀 수 있는 문제이다. 1. 상어가 움직일 때 현재 map의 R크기와 C크기에 따른 상어의 속력 s를 활용하여 움직인 후의 위치 찾아주기 2. PriorityQueue를 활용하여 상어의 크기가 큰 순으로 offer하기 → 상어가 모두 움직인 후 map에 위치시킬 때 해당 칸에 이미 상어가 존재한다면 현재 상어는 잡아먹히게 되는 것임 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; im.. 2022. 11. 7. 이전 1 2 3 4 5 ··· 12 다음
