BOJ (326) 썸네일형 리스트형 [BOJ] 백준 4386 별자리 만들기 (Swift) 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 좌표 평면에서 MST를 만드는 문제입니다. 간선이 주어지지 않았기 때문에 직접 간선을 구해주어야 합니다. 두 별 사이의 모든 거리를 구해주어야 합니다. 프로퍼티로는 시작노드, 도착노드, 비용을 갖는 Edge 구조체를 선언해주었습니다. 두 별 사이의 모든 거리를 구해주고, 구조체 배열에 넣어줍시다. 이제 크루스칼 알고리즘을 사용하여 최소 비용을 구할 수 있습니다. 거리를 기준으로 오름차순으.. [BOJ] 백준 1197 최소 스패닝 트리 (Swift) 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 문제 그대로 최소 스패닝 트리(MST)를 구하는 문제입니다. 최소 스패닝 트리를 구하는 방법으로는 크루스칼 알고리즘, 프림 알고리즘을 활용해서 구할 수 있습니다. 저는 크루스칼 알고리즘을 활용하여 풀이하였습니다. 간선을 비용의 오름차순 순으로 정렬하여, 비용이 적은것 부터 확인하면서 사이클이 이루어지지 않는다면 연결시켜 줍시다. 연결시킨 비.. [BOJ] 백준 9372 상근이의 여행 (Swift) 문제 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이 약간 넌센스? 같은 문제입니다. 비행 스케줄은 항상 연결 그래프이기 떄문에, n개국을 여행하기 위한 최소의 경로는 n - 1 개입니다. 소스코드 후기 최소 스패닝 트리로 분류되어 있어서, 간선의 비용을 모두 1로 하고 제거해봐야 했는데.. 그럴필요가 없는 문제였습니다. [BOJ] 백준 20040 사이클 게임 (Swift) 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 유니온 파인드 알고리즘을 활용하여 풀이할 수 있는 문제입니다. 사이클이 완성되는 경우는 어떠한 경우일까요? 현재 1, 2, 3이 다음과 같이 연결되어있다고 가정해봅시다. 현재 2와 3의 부모노드는 1로 같습니다. 2와 3을 연결하면 사이클을 발생시킵니다. 즉, 같은 부모노드를 가진 것 끼리 연결하게 된다면 사이클이 생성되게 됩니다. 그러므로, 연결을 하기 전에 같은 두 노드가 같은.. [BOJ] 백준 4195 친구 네트워크 (Swift) 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온 파인드로 풀이할 수 있는 문제입니다. 노드가 Int가 아닌 String 값이기 때문에, [String: String] 의 딕셔너리로 선언해주었습니다. 관계의 노드 수를 구하기 위해 level이라는 [String: Int]의 딕셔너리를 선언해주었습니다. 초기 입력받을 때, 부모노드를 자기 자신으로 초기화 해주고, level도 1로 초기화 해주었습니다. 부모 노드를 찾는 .. [BOJ] 백준 1976 여행 가자 (Swift) 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드 알고리즘으로 풀이할 수 있는 문제입니다. https://dev-mandos.tistory.com/296 [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음.. [BOJ] 백준 1717 집합의 표현 (Swift) 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드로 풀이할 수 있는 문제입니다. https://dev-mandos.tistory.com/296 [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Un.. [BOJ] 백준 4803 트리 (Swift) 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 무방향 그래프에서 사이클이 있는 지 판별해야 하는 문제입니다. 여러 방법이 있겠지만 저는 DFS를 사용하였습니다. 무방향 그래프이기 때문에 1번 노드와 2번 노드가 연결되어 있다면, 1 -> 2, 2 -> 1 로 가능하기에 사이클이 존재한다고 할 수 있지만, 이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 .. 이전 1 ··· 5 6 7 8 9 10 11 ··· 41 다음
