본문 바로가기
728x90

알고리즘42

[백준17472] 다리 만들기2[java] 정말 어려운 문제였다. bfs와 크루스칼 알고리즘을 사용해야 했다. 우선 첫단계로는 입력받은 숫자들을 bfs를 이용해 섬의 번호를 붙여줬다. 두번째 단계로는 섬에서 상하좌우중 한 방향으로만 나아가다가 다른 섬을 만났을 때 시작섬과 끝섬, 그 길이를 edge클래스로 만들고 우선순위 큐에 넣는다. 마지막으로는 우선순위큐에서 하나씩 꺼내 크루스칼 알고리즘을 이용해 순환하지 않는 최단거리를 찾았다. 코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; im.. 2021. 4. 7.
[백준2887] 행성터널[java] 문제에서 최소비용을 계산할 때 x,y,z의 거리중 가장 작은 값의 비용이 든다고 했다. x,y,z로 각각 오름차순으로 정렬한 뒤 가중치를 구해서 한번에 저장한다. 그 후에 find-union알고리즘을 이용해 순환하지 않게 최소값을 구하면 된다. 코드 package baekjoon; import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class planet_tunnel { static class Point{ int num,x,y,z; Point(int num, int x, int y, int z){ this.. 2021. 4. 5.
[백준 1774] 우주신과의 교감[java] 기존의 최소 스패닝 트리 문제와는 다르게 두개의 클래스를 만들어 줘야합니다. 하나는 신들의 좌표와 순번을 갖는 Point 클래스, 다른 하나는 한 신에서 다른 신으로 갈때 Point와 그 가중치를 갖는 edge클래스입니다. Point 클래스 static class Point{ int num; double x,y; Point(int num,double x, double y){ this.num = num; this.x = x; this.y = y; } } Edge클래스 static class Edge implements Comparable{ int start; int end; double weight; Edge(int start, int end, double weight){ this.start = start.. 2021. 4. 5.
[백준 1197] 최소 스패닝 트리[java] 제목 그래도 가장 기본적인 최소 스패닝 트리 문제였다. 크루스칼 알고리즘을 통해 문제를 풀었다. 크루스칼 알고리즘은 간선의 가중치가 가장 작은 것을 고르고 사이클이 생기지 않는 노드만 방문 하는 것이다. 결국 두 가지 핵심으로 나눌 수 있다. 하나는 가중치가 작은 것을 고르기 다른 하나는 어떻게 사이클이 생기지 않게 하기이다. 가중치가 작은 것 고르기는 우선순위큐에 간선을 기준으로 넣어주면 된다. 그럼 저절로 가중치가 작은 순서대로 저장할 수 있다. 사이클이 생기지 않게 하기는 union-find알고리즘을 이용하면 된다. 노드의 최종 부모가 누구인지를 확인하는 방법인데 시작노드와 끝노드의 최종 부모가 같으면 사이클이 생기는 것이다. 코드 package baekjoon; import java.io.Buff.. 2021. 4. 5.
[백준2206] 벽 부수고 이동하기[java] 매우 쉬운 bfs문제인거 같지만 벽을 한번 부수고 갈 수 있다는 조건이 생각보다 까다로웠다. bfs방법으로 탐색을 하다보니 방문을 하다보며  매우 쉬운 bfs문제인거 같지만 벽을 한번 부수고 갈 수 있다는 조건이 생각보다 까다로웠다. bfs방법으로 탐색을 하다보니 방문을 하다보며 한 노드에 관해서 벽을 부순 길이 지나가다가 들릴수도 있고 부수지 않은 길이 그 노드를 지날 수 있다. if(nx>=0 && ny>=0 && nx 2021. 4. 2.
[백준 7562] 나이트의 이동 [java] bfs를 이용하여 매우 쉽게 해결한 문제이다. 다른 문제랑 달랐던 부분은 나이트의 이동이기 때문에 움직이는 곳이 상,하,좌,우가 아니라 8곳이나 된다는 것이었다. 하지만 그 부분은 전역 배열을 선언해둬서 쉽게 해결해줬고 요번 문제는 x와 y의 class를 따로 만들지 않고 queue에 x따로 y따로 만들어 줘봤다. 코드 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class knight_move { static int[] dx = {-2,-1,2,1,-2,-1,1,2}; static int[] dy = {1,2,1,2,-1,-2,-2,-1}; static int[].. 2021. 4. 1.
728x90

티스토리툴바