본문 바로가기
반응형

전체 글133

백준 18405번 : 경쟁적 전염 java 이 문제는 우선순위 큐를 이용하여 입력을 받아준 후 bfs를 이용하면 되는 문제입니다. 이 문제에서는 N x N 크기의 시험관에서 K종류의 바이러스가 존재한다고 합니다. 그리고 이 바이러스는 숫자가 낮은 바이러스부터 차례대로 주변으로 한 칸씩 증식합니다. 이때 바이러스가 증식하는 순서를 정렬하기 위해서 PriorityQueue를 사용해줍니다. 그리고 각 초마다 증식하기 때문에 각 초마다 주변으로 1칸씩 우선순위 큐에 들어있는 순서대로 증식하게 만듭니다. 그리고 (3, 2) 칸에 바이러스가 존재한다면 바로 종료하도록 만들었습니다. 바로 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int N; static.. 2022. 7. 1.
백준 1707번 : 이분 그래프 java 이 문제는 이분 그래프인지 아닌지를 확인하는 문제입니다. 우선 이분 그래프가 무엇인지에 대해서 설명드리겠습니다. 이분 그래프란 위의 그림과 같이 연결된 두 정점의 색깔을 다르게 칠할 수 있는 그래프입니다. 위의 그림과 같이 빨간 간선이 추가되어 연결된 두 노드의 색깔이 같다면 이는 이분 그래프라 말할 수 없습니다. 그래프가 이분 그래프인지 확인하는 방법은 dfs를 이용하는 방법과 bfs를 이용하는 방법이 있습니다. 저는 이 중에서 dfs를 이용하였습니다. 하나의 정점을 선택한 후 dfs를 이용하여 이동할 때 이동한 간선이 이전의 간선과 다른 타입으로 만들 수 있는지를 확인하면서 진행하였습니다. 이미 방문한 정점이라도 다른 타입인지를 확인하게 만들었습니다. 코드를 보여드리도록 하겠습니다. import ja.. 2022. 6. 30.
백준 1717번 : 집합의 표현 java 이 문제는 분리 집합을 이용하여 해결하는 문제입니다. 분리 집합이란 union-find 함수를 이용하여 자신과 연결되어 있는 정점인지 확인하여 연결되어 있지 않다면 연결하는 알고리즘입니다. 이 문제에서는 0이 처음 입력으로 주어졌을 경우 뒤의 두 정점을 이어주고 1이 입력으로 들어올 경우 두 정점이 연결되어 있는지를 확인하여 YES나 NO를 출력하면 됩니다. 코드를 바로 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(ne.. 2022. 6. 30.
백준 1043번 : 거짓말 java 이 문제는 지민이가 이야기하는 것에 대한 진실을 아는 사람이 주어질 때 이 사람들과 같은 파티에 갔던 사람들에게 들키지 않고 지민이가 얼마나 많은 파티에서 거짓말을 할 수 있는지 구하는 문제입니다. 이 문제를 풀 때 우선 지민이가 말한 것에 대한 진실을 아는 사람들을 입력받습니다. 그리고 그 사람들과 같은 파티에 갔던 사람들을 union-find를 이용하여 합쳐줍니다. 그리고 그 사람들이 갔던 파티를 제외한 다른 파티의 개수를 세어 출력하면 됩니다. 이에 대한 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws.. 2022. 6. 29.
백준 1976번 : 여행 가자 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 분리 집합이란 여러 개의 분리된 집합들이 있을 때 이 집합들에 대한 연결 관계를 입력받아 연결하여 이를 이용하는 문제입니다. 이 문제에서는 N개의 도시에 대한 연결 관계를 입력받아서 M개의 도시를 여행할 수 있는지 확인하는 문제입니다. 한번 갔던 도시라도 연결되어 있기만 하다면 갈 수 있습니다. 코드를 바로 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new In.. 2022. 6. 29.
백준 20040번 : 사이클 게임 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 첫 번 째 줄에서 N과 M을 받은 후 N개의 정점에서 M개의 선을 이을 때 사이클이 생기지 않으면 0을 출력하고 사이클이 생기면 사이클이 생겼을 때 입력받은 간선의 수를 출력하는 문제입니다. 예제 1번은 모든 간선을 이어도 아래와 같이 사이클이 없으므로 0을 출력합니다. 하지만 예제 2번은 중간에 사이클이 생깁니다. 언제 사이클이 생기는지 보여드리겠습니다. 첫 번째 간선을 입력받았을 때 다음과 같은 모습입니다. 두번째 입력을 받았을 때 위와 같은 모습입니다. 세번째 입력을 받았을 때 다음과 같은 모습입니다. 그리고 네번째 입력을 받을 때 사이클이 생깁니다. 따라서 4를 출력합니다. 이 문제를 풀면서 그래프가 생기는가 생기지 않는가는 union-find 함.. 2022. 6. 29.
백준 1261번 : 알고스팟 java 이 문제는 벽을 최대한 적게 부수면서 (1, 1)에서 (N, M)까지 갈 때 부순 벽의 개수를 출력하는 문제입니다. 이 문제를 언뜻 보았을 때 dfs를 이용해서 벽을 부수면서 탐색해야 할 것처럼 보입니다. 하지만 이 문제는 끝까지 갔을 때 부순 벽의 개수가 최소가 되어야합니다. 따라서 bfs를 이용해서 주변을 탐색하며 끝까지 가장 벽을 적게 부수고 가는 경우의 수를 찾아야 합니다. 이를 위해서 PriorityQueue에 각각의 노드의 정보와 벽을 몇 개를 부수었는지에 대한 정보를 넣고 벽을 부신 개수를 오름차순으로 정렬하여 벽을 가장 적게 부수고 끝 점까지 가는 방법을 찾아야 합니다. 이에 대한 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; publi.. 2022. 6. 27.
백준 1068번 : 트리 java 이 문제는 트리를 이용하는 문제로 트리를 만들고 노드를 추가, 삭제한 다음 리프 노드의 개수를 세는 문제입니다. 이 문제를 풀 때 조심해야하는 점은 0번이 아닌 다른 노드가 루트 노드가 될 수 있고 이진트리라는 말이 없기 때문에 자식 노드가 3개 이상일 수 있다는 것입니다. 이러한 점 때문에 이 문제에서 쓸 트리를 배열에 저장하는 방식을 통해서 만들었습니다. parent 배열은 만들어 자신의 부모 노드를 저장할 배열을 만든 후 노드가 제거되면 그 자식 노드까지 제거되도록 dfs를 이용하였습니다. 코드를 바로 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N; static int[] parent; static b.. 2022. 6. 26.
반응형

티스토리툴바