Swift (356) 썸네일형 리스트형 [BOJ] 백준 1774 우주신과의 교감 (Swift) 문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 MST를 구하기 위해 크루스칼 알고리즘으로 풀이할 수 있는 문제입니다. 모든 우주신의 좌표와 좌표사이의 거리를 직접 구해주어야 합니다. 즉, 노드간의 간선을 구해주어야 합니다. 그 이후 통로의 개수는 합집합 연산을 통해 미리 합쳐주고, 간선의 비용을 오름차순으로 정렬을 하고, 사이클이 이루어지지 않는다면 이어줍시다. 그렇다면 최소 비용을 구할 수 있습니다. 소.. [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 연산으로 이루어져있음.. [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음 위의 이미지에서 1과 6이 같은 그래프에 속하는지 판별할 수 있는 알고리즘 입니다. Find 연산 부모노드를 찾는 Find 연산을 구현하려 합니다. parent 라는 이름을 지어준 Int 배열을 사용할 것이고, parent[1] = 3 의 의미는 1번 노드의 부모는 3이다. 라고 정의할 수 있습니다. 먼저, 아무 노드도 연결되어 있지 않다고 가정한다면 현재 노드의 부모노드는 자기 자신일 것입니다. 0번 인덱스는 사용하지 않고, 단순히 번호를 맞춰주기 위해서 0번 인덱스부터 시작하였습니다. 이 그림과.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 45 다음
