본문 바로가기

Algorithm43

[BOJ 백준] 2606번 바이러스 - 자바 문제 : 2606번 바이러스 접근 유형 : bfs, 그래프 아래와 같은 조건을 파악 후 bfs를 사용하여 풀어야겠다고 생각했습니다. bfs를 통해 현재 노드와 인접한 노드를 큐에 넣고 방문할 수 있게 됩니다. 예시로서 아래와 같은 그림이 주어집니다. 이 그림을 보고, 노드와 간선으로 이루어진 그래프임을 알 수 있었으며, 연결 리스트 형태로 저장해야겠다고 생각했습니다. 특히, 1->2, 2->1로도 갈 수 있는 그래프 형태로서, 연결 리스트는 양방향으로 저장해야 함을 알 수 있었습니다. - 구현 코드는 다음과 같습니다. 주의 사항 : 연결리스트 초기화가 필수입니다!! public class Main { private static LinkedList list; private static boolean[] v.. 2022. 8. 30.
[Algorithm] Union-Find 최소 신장 트리를 표현하기 위해 사용되는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 존재합니다. 이 알고리즘을 구현하는 과정에서 Union-Find 자료구조가 사용됩니다. 특히, 사이클을 판별하는 과정에서 서로소 집합을 활용하여 사이클을 판별할 수있습니다. 서로소 집합을 표현하기 위해 Union-Find 자료구조를 사용합니다. 서로소 집합 : 공통 원소가 없는 두 집합입니다. {1}와 {2,3,4}는 서로 공통 원소가 없으므로 서로소 집합이라고 할 수 있습니다. Union Find의 연산의 종류 makeSet(x) : 자기 자신의 원소 번호 자신이 속해있는 집합으로 초기화하며, 크기가 1인 서로소 집합 생성하게 됩니다. find(x) : x가 속한 집합의 부모(대표가 되는 값)을 반환합니다. unio.. 2022. 8. 25.
[SWEA] 7465 창용 마을 무리의 개수 - 자바 문제 접근 : DFS 고려 요소 양방향이므로 양방향 간선으로 저장해야 합니다. 또한, 연결리스트를 통해 이러한 간선에 대해 표현하였습니다. 연결리스트 초기화 필수!! 노드는 1~N번 모든 노드에 대해 DFS를 탐색해야하며, 이미 방문한 노드(이미 그룹이 됨)는 탐색을 수행하지 않도록 boolean배열을 사용합니다. public class Solution_7465 { private static List node; private static boolean[] visited;//방문 여부 확인 private static int N;//마을에 사는 사람의 수 public static void main(String[] args) throws NumberFormatException, IOException { Buf.. 2022. 8. 24.
[Algorithm] 비트마스크 오늘은 부분집합을 비트연산자를 통해 구현하는 방법에 대해 알아보겠습니다. bit 1인 경우, 그 위치에 맞는 집합의 숫자를 출력하는 형태를 통해 모든 부분 집합의 경우의 수를 나타낼 수 있습니다. 특히, 부분집합의 개수는 2^N으로 표현되는데, 이를 1 2022. 8. 22.

티스토리툴바