본문 바로가기
728x90

분류 전체보기138

[백준 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.
[백준4386] 별자리 만들기 [java] 이 문제는 크르수칼 알고리즘과 union-find알고리즘으로 풀었다. 각 점들의 길이가 가중치가 되므로 모든 길이를 구한 뒤 그 길이를 오름차순으로 정렬시킨다 순서대로 가중치에 따른 시작점과 끝점을 보고 순환하게 되지 않는다면 결과값에 더해주면 된다. 코드 package baekjoon; import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; class Point1{ int num; double x; double y; Point1(int num, double x, double y){ this.num = num; this.x = x; this.y = y; } } cl.. 2021. 3. 31.
[백준 9372] 상근이의 여행 [java] 이 문제는 간단한게 bfs문제로 풀면 가능한 문제다. 배열을 만들때 1부터 시작한다는 것만 생각해주면 된다! 코드 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class sanggeun_travel { static int arr[][]; static boolean visit[]; static int country, line, result; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i = 0; i 2021. 3. 31.
728x90

티스토리툴바