본문 바로가기
반응형

분류 전체보기123

백준 2211번 : 네트워크 복구 java 이 문제는 다익스트라 알고리즘을 이용하여 1번 컴퓨터에서 각 컴퓨터로 향하는 최단 경로를 구하고 그 경로를 출력하는 문제입니다. 저는 이를 위하여 PriorityQueue 안에 각각의 노드에는 목표 정점(to)과 그 정점으로 가기 직전의 정점(from), 시작 정점에서 목표 정점까지의 거리(val)를 저장하였습니다. 그리고 각 정점에 처음 방문하였을 때 to와 from을 다른 ArrayList에 담아 최단 경로를 저장하였습니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static List answer = new ArrayList(); public static.. 2022. 7. 27.
백준 2638번 : 치즈 java 이 문제는 (0, 0)에서 bfs를 실행하여 위의 그림 1, 2, 3과 같이 바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제입니다. 저는 각각의 치즈가 주변에 공기가 몇 칸이 있는지를 확인하기 위해서 air 배열을 이용하였습니다. import java.io.*; import java.util.*; public class Main { static int N, M, cheeseNum = 0, time = 0; static int[][] map; static int[][] air; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args.. 2022. 7. 26.
백준 2637번 : 장난감 조립 java 이 문제는 위상 정렬을 이용하여 부품을 만들어야 하는 우선순위를 만든 뒤 우선순위에 있는 부품을 만들기 위해서 필요한 우선순위가 뒤에 있는 부품의 개수를 더하며 푸는 문제입니다. 위의 예제 입력 1번을 예시로 설명하겠습니다. 예제 입력 1번의 N은 7입니다. N은 만들어야하는 개수가 1개입니다. 7을 만들기 위해서는 우선 6을 3개, 5를 2개, 4를 5개 만들어야 합니다. 그리고 6을 1개 만들기 위해서는 3을 3개, 4를 4개, 5를 2개 만들어야 합니다. 이때 6을 3개 만들어야 하므로 3을 3x3인 9개, 4를 12개, 5를 6개 만들어야 합니다. 그리고 5를 만들기 위해서는 1을 2개, 2를 2개 만들어야 합니다. 5는 7을 만들기 위해서 2개, 6을 만들기 위해서 6개가 필요해 총 8개가 필요.. 2022. 7. 25.
백준 1766번 : 문제집 java 이 문제는 위상 정렬과 우선순위 큐를 이용하여 푸는 문제입니다. 먼저 푸는 것이 좋은 문제들이 존재하여 이를 조건에 맞게 정렬해주는 위상 정렬 알고리즘을 사용하고 문제를 풀 때 낮은 번호의 문제를 먼저 푸는 것이 좋기 때문에 우선순위 큐를 이용하여 낮은 번호의 문제를 뽑아내야 합니다. 위의 예제를 살펴보도록 하겠습니다. 위 문제는 위와 같은 구조를 이루고 있습니다. 1번과 2번 문제는 각각 3번, 4번 문제를 먼저 해결해야 하므로 parentNum이 1입니다. 이제 parentNum이 0이라서 먼저 풀어도 상관없는 정점들을 PriorityQueue에 넣어줍니다. 이제 PriorityQueue의 가장 앞에 있는 문제를 풀어주겠습니다. 3번 문제를 풀었으니 이제 1번 문제의 parentNum이 0이 되어 풀.. 2022. 7. 24.
백준 1719번 : 택배 java 이 문제는 각각의 번호마다 다익스트라 알고리즘을 적용하여 각각의 정점마다 다른 정점까지 갈 때의 최단경로에서 처음으로 거쳐가는 정점을 출력하는 문제입니다. 저는 최단 경로에서 처음 거쳐가는 정점을 구하기 위해서 firstGo라는 배열을 따로 만들어서 이 정점에 오기 위해서 처음 거쳐야 하는 정점을 저장하게 만들었습니다. 이 firstGo라는 배열은 초기값으로 자기 자신의 정점 번호를 가지고 있습니다. 그리고 시작 정점에서 다른 정점을 거쳐서 자신의 정점으로 오는 것이 더 효율적이라면 firstGo 배열에서 그 정점의 인덱스에 저장되어 있는 정점을 저장하게 하는 식으로 최단 경로에서 처음 간 정점을 구하게 만들었습니다. 위의 그림과 같은 그래프가 있다고 가정하겠습니다. 이 그래프를 이용하여 다익스트라 알고.. 2022. 7. 23.
백준 5972번 : 택배 배송 java 이 문제는 다익스트라 알고리즘을 이용하는 기초 문제입니다. 다익스트라 알고리즘에 대한 설명은 아래의 링크에 있습니다. 백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] dist; public static void main(String[] args) throws IOExceptio.. 2022. 7. 22.
백준 4485번 : 녹색 옷 입은 애가 젤다지? java 이 문제는 다익스트라 알고리즘을 이용하여 (0, 0)에서 (N-1, N-1)까지 갈 때까지 최소한으로 소지금을 잃으면 서 갈 수 있는 경로를 찾는 문제입니다. 우선 (0, 0)에서 시작하여 주변 정점들의 비용을 확인하면서 더 비용이 적게 드는 경로를 선택하여 진행하면 됩니다. import java.io.*; import java.util.*; public class Main { static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader.. 2022. 7. 21.
백준 16562번 : 친구비 java 이 문제는 분리 집합을 이용하여 학생들이 서로 친구인지 아닌지 확인하면서 친구비를 지불하는 문제입니다. 이 문제에서는 한 무리의 학생들이 서로 친구일 경우 가장 적은 친구비를 주어도 되는 학생을 찾아 친구비를 지불하면 됩니다. 위 문제의 예제 1번은 다음과 같이 친구관계를 맺고 있습니다. 이 문제에서는 1, 3번 학생이 친구이고 2, 4, 5번 학생이 친구입니다. 따라서 이 그룹 중에서 각각 한 명씩만 친구가 되면 됩니다. 1번 학생의 친구비가 10이고 3번 학생의 친구비가 20이니 1번 학생에게 친구비를 지불해줍니다. 2번 학생의 친구비가 10이고 4번 학생의 친구비가 20, 5번 학생의 친구비가 30이니 2번 학생에게 친구비를 지불합니다. 따라서 20의 금액만 있다면 주어진 모든 학생들과 친구가 될 .. 2022. 7. 20.
반응형

티스토리툴바