분류 전체보기 (400) 썸네일형 리스트형 [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번 인덱스부터 시작하였습니다. 이 그림과.. [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 로 가능하기에 사이클이 존재한다고 할 수 있지만, 이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 .. [BOJ] 백준 1991 트리 순회 (Swift) 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 재귀를 사용하여 풀 수 있습니다. 저는 Node라는 구조체 하나를 선언하여, left와 right 프로퍼티를 선언해주었습니다. 이는 자식노드의 왼쪽, 오른쪽을 표현합니다. 입력을 받아서 [String: Node] 의 딕셔너리 컬렉션에 값을 추가하였습니다. 모든 순회가 "A" 노드부터 시작됩니다. preorder의 경우 루트 -> 왼쪽 -> 오른쪽 순으로 탐색을 진행합니다. 함.. [BOJ] 백준 1967 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/291 [BOJ] 백준 1167 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정 d.. [BOJ] 백준 1167 트리의 지름 (Swift) 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 DFS를 사용해서 풀 수 있습니다. 임의의 노드에서 출발하여 가장 먼 거리에 있는 노드를 탐색해줍시다. 임의의 노드에서 출발하여 가장 먼 거리에 있는 노드는 트리의 지름에 포함되는 노드입니다. 가장 먼 거리에 있는 노드를 찾았다면 그 노드에서 부터 가장 깊은 곳이 트리의 지름이 됩니다. 소스코드 후기 처음에는 모든 노드에 대해 DFS나 다익스트라를 해봐야하나... 생각이.. 이전 1 ··· 11 12 13 14 15 16 17 ··· 50 다음
