본문 바로가기
반응형

전체 글133

백준 16236번 : 아기 상어 java 이 문제는 bfs를 이용해서 아기 상어가 엄마 상어에게 도움을 받지 않고 얼마나 물고기를 먹으러 이동할 수 있는지를 구하는 문제입니다. 이 문제의 초기 조건은 아래와 같습니다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 여기서 아기 상어가 상하좌우로 1칸씩 이동할 수 있다는 것에서 bfs를 사용할 수 있을 것이라는 생각을 했습니다.. 2022. 6. 25.
백준 1504번 : 특정한 최단 경로 java 이 문제는 다익스트라 알고리즘을 이용하여 중간에 정점 v1과 v2를 거쳐 N으로 갈 때의 최단 경로의 길이를 구하는 문제입니다. 이 문제를 풀기 위해서는 우선 정점 1에서 v1과 v2로 갈 때의 최단 경로의 길이를 구해야 합니다. 만약 경로가 존재하지 않을 경우에는 그다음 단계를 진행하지 않아도 됩니다. 1에서 v1으로 가는 경로가 없다고 가정하면 1에서 v2로 가는 최단 경로를 구하고 그 후 v2에서 v1으로 가는 최단 경로를 구해야 합니다. v2와 v1을 모두 거쳐야 하기 때문에 이 경로를 구해줍니다. 그리고 마지막으로 v1에서 N으로 가는 최단 경로를 구한 후 이 3개의 경로의 길이를 더한 값을 출력합니다. 이에 대해서 예제 1번을 예시로 설명드리겠습니다. 위 그림은 예제 1번을 나타낸 그림입니다... 2022. 6. 25.
백준 2589번 : 보물섬 java 이 문제는 bfs를 이용하여 섬 안에서 가장 먼 거리에 보물을 묻을 때 보물 간의 거리를 구하는 문제입니다. 이 문제를 풀 때는 브루트포스 알고리즘을 사용해야 합니다. 지도의 각 칸을 탐색하면서 탐색한 칸이 땅일 때 연결된 땅들을 전부 탐색하면서 가장 거리가 먼 땅을 찾습니다. 코드를 보면서 조금 더 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int row, col; static char[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int max = 0; public static void main(Strin.. 2022. 6. 24.
백준 1238번 : 파티 java 이 문제는 다익스트라 알고리즘을 이용하여 학생들이 파티를 참가하기 위해 한 마을로 모였다가 다시 자신의 마을로 돌아갈 때 가장 시간이 오래 걸리는 학생의 소요시간을 구하는 문제입니다. 이 문제를 푸는 방법은 2가지가 있습니다. 우선 첫 번째의 방법은 플로이드 와샬 알고리즘을 이용하여 각각의 학생들이 오고 갈 때의 시간을 구하는 방법이 있습니다. 하지만 이 방법을 사용한다면 시간 복잡도가 O(n^3)이 되어 시간이 오래 걸리게 됩니다. 이 문제에서는 플로이드 와샬 알고리즘을 써도 맞다고는 나오지만 N이 더 늘어나면 시간이 메모리를 더 많이 쓰게 되므로 좋은 정답이 아닙니다. 우선 플로이드 와샬 알고리즘으로 이 문제를 풀었을 때를 보여드리겠습니다. import java.io.*; import java.uti.. 2022. 6. 24.
백준 2468번 : 안전 영역 java 이 문제는 배열의 각 칸을 순회하면서 bfs를 이용하여 연결된 안전 영역들을 탐색하는 문제입니다. 연결된 안전 영역들의 개수를 파악하는 문제입니다. 코드를 보면서 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N, safe = 0; static int minHeight = Integer.MAX_VALUE; static int maxHeight = Integer.MIN_VALUE; static int[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args) th.. 2022. 6. 23.
백준 2580번 : 스도쿠 java 이 문제는 스도쿠 문제를 백트래킹을 이용하여 푸는 문제입니다. 위와 같은 스도쿠 판이 있다고 가정하겠습니다. 이 스도쿠 판에서 빈칸들을 채우기 위해서는 아래와 같이 가로, 세로, 박스 안을 확인해야 합니다. 이 세 영역에 빈칸에 넣는 수와 같은 수가 존재하지 않아야 빈칸에 수를 삽입할 수 있습니다. 코드를 보면서 이 문제의 풀이에 대해 더 자세히 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[][] board; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputSt.. 2022. 6. 23.
백준 16234번 : 인구 이동 java 이 문제는 데이터들을 입력 받아서 주변과의 차이가 L 이상, R 이하라면 각각의 셀에 있는 값들을 모두 더해서 평균값으로 만들어주는 알고리즘입니다. 예제 1번을 보시면 이를 더 잘 이해하실 수 있습니다. 코드를 보면서 추가로 설명해드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int N, L, R; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int[][] map; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRe.. 2022. 6. 23.
백준 15655번 : N과 M (6) java 이 문제는 입력 받은 배열을 정렬한 후 자신 이후의 인덱스에 있는 자료들을 M개 만큼 출력하는 문제입니다. 이 문제를 해결하기 위해서는 재귀적으로 함수를 불러오면서 불러온 횟수가 M번이 되면 출력하면 됩니다. 코드를 보시면 쉽게 이해하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { static int N, M; static int[] data; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String.. 2022. 6. 22.
반응형

티스토리툴바