[SWEA] - 하나로 / 1251번 (Java)

[SWEA] - 하나로 / 1251번 (Java) [SWEA] - 하나로 / 1251번 (Java) 1. 문제 접근 각 섬의 좌표가 주어지고, 각 섬을 연결하고자할 때 섬을 연결하는 최소 비용을 계산 하면 되는 문제다. 최소 비용으로 모든 섬을 연결하기 위해 MST(Kruskal) 알고리즘을 통해 구현했다. 구현의 흐름은 다음과 같다. 간선의 정보가 주어지지 않았으므로, 완전그래프 형태로 모든 간선을 생성하여 간선 리스트에 저장한다. 간선 리스트를 환경부담금(`cost`)을 기준으로 오름차순으로 정렬한다. 환경부담금(`cost`)이 작은 간선부터 트리에 연결한다. 이 때, 사이클이 생길 경우 해당 간선은 제외한다. 간선의 개수가 V-1(V: 섬 개수)가 된다면 종료한다. 완전 그래프에서 간선의 개수는 V..

• format_list_bulleted 알고리즘
• · 2024. 2. 22.
• textsms

[SWEA] - 최소 스패닝 트리 / 3124번 (Java)

[SWEA] - 최소 스패닝 트리 / 3124번 (Java) [SWEA] - 최소 스패닝 트리 / 3124번 (Java) 1. 문제 접근 MST의 가장 기본적인 예제로 크루스칼 알고리즘과 Union-Find알고리즘을 통해 구현하였다. 크루스칼 알고리즘을 이용한 MST의 흐름은 다음과 같다. 무향 가준치 그래프에서 주어진 간선의 정보를 저장한다. 간선의 정보를 가중치를 기준으로 오름차순으로 정렬한다. 간선의 가중치가 작은 순서대로 트리를 완성시킨다. 이 때, 사이클이 발생한다면 해당 간선은 추가하지 않는다. 간선의 개수가 V-1개(V: 정점의 개수)가 되면 반복을 중단한다. 2. 코드 package swea; import java.io.BufferedReader; import java.io.InputStr..

• format_list_bulleted 알고리즘
• · 2024. 2. 22.
• textsms

[SWEA] - 서로소 집합 / 3289번 (Java)

[SWEA] - 서로소 집합 / 3289번 (Java) [SWEA] - 서로소 집합 / 3289번 (Java) 1. 문제 접근 총 n개의 단일 원소를 갖는 집합에 대해 `0`(두 집합을 합치기), `1`(두 집합이 거로 같은 집합에 속하는지) 연산을 실행하고 `1`번 연산에 대해 결과를 출력하면 된다. 기본적인 Union Find 알고리즘이다. Union Find에는 총 3개의 연산이 존재한다 `makeSet()`: 초기 집합 상태를 만드는 연산 `union()`: 두 집합을 하나의 집합으로 합치는 연산 `getRoot()`: 특정 노드의 집합을 식별하는 연산 따라서 `0`번 입력이 들어오면 `union()`을, `1`번 연산이 들어오면 `getRoot()`연산을 통해 결과를 얻으면 된다. switch ..

• format_list_bulleted 알고리즘
• · 2024. 2. 21.
• textsms

[SWEA] - 상호의 배틀필드 / 1873번 (Java)

[SWEA] - 상호의 배틀필드 / 1873번 (Java) 1. 문제 접근 초기 게임 맵이 주어지고, 전차의 움직임을 통해 이후 변화된 게임 맵의 상태를 출력하면 된다. 주어진 명령어 배열`char[] command`를 통해 각각의 명령에 대해 주어진 맵을 수정하면 되는 문제였다. 초기 맵 초기화를 하고 전차의 상태를 함께 초기화한다. for (int row = 0; row ') { // dir = 3: 우 tankStatus = new Tank(row, col, 3); } else if (map[row][col] == '') { // dir = 3: 우 tankStatus ..

• format_list_bulleted 알고리즘
• · 2024. 2. 15.
• textsms

[SWEA] - 최적 경로 / 1247번 (Java)

[SWEA] - 최적 경로 / 1247번 (Java) 1. 문제 접근 회사에서 출발해서 모든 고객의 집을 방문하고 자신의 집까지 도달하는 최단 경로를 구하면 되는 문제다. 이 때, 시작지점은 회사로, 종료지점은 집으로 고정되어있다는 것을 인지해야한다. 시작지점과 종료지점을 고정해두면, N명 고객의 집을 방문하는 순서만 고려하여 방문하면된다. 고객의 수`N`은 최대 10이라는 조건을 통해 완전 탐색(순열)을 이용한 풀이를 떠올렸다. 하지만, 10! = 3,628,800으로 완전 탐색을 돌려도 되지만, 백트래킹을 통해 시간복잡도를 최적화 할 수 있을 것 같다는 생각이 들었다. 백트래킹의 Pruning할 수 있는 경우를 생각해보면, n번째 순열을 구성하며 현재 위치(고객의 집)까지 도달하는 거리가 n-1번째 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 15.
• textsms

[SWEA] - 무선 충전 / 5644번 (Java)

[SWEA] - 무선 충전 / 5644번 (Java) 1. 문제 접근 모든 사용자의 충전량 합의 최대값을 구하면 된다. 사용자는 A, B 2명만 존재하며, 주어진 시간 `totalTime` 동안 이동시킨다. 문제에서 주어진 그림을 기준으로 상하좌우를 보면 아래와 같이 이동한다. 상(열 감소) 우(행 증가) 하(열 증가) 좌(행 감소) 또, A B 2명이 항상 큰 충전량을 가지는 BC를 선택하기 위해 BC의 충전량을 기준으로 내림차순 정렬한다. // BC 클래스 static class BC implements Comparable{ Pos pos; int limitDist; int power; public BC(int xPos, int yPos, int limitDist, int power) { pos = ..

• format_list_bulleted 알고리즘
• · 2024. 2. 15.
• textsms