PS/백준 (318) 썸네일형 리스트형 [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 로 가능하기에 사이클이 존재한다고 할 수 있지만, 이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 .. [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나 다익스트라를 해봐야하나... 생각이.. [BOJ] 백준 11725 트리의 부모 찾기 (Swift) 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 문제 그대로 트리에서 각 노드의 부모를 찾는 문제입니다. 루트노드를 1로 정하였으므로, 입력에서 주어진 간선들을 연결시켜 줍시다. 1에서부터 BFS, DFS를 사용해서 노드들에 대해서 탐색한다면, 다음 탐색할 노드가 현재 노드의 자식노드가 됩니다. 트리의 부모를 찾기 위해 parent라는 Int 배열을 사용하였고, 값을 -1로 초기화하였습니다. 인덱스를 현재 노드, 값을 부모 노드의 번호로 사용하려고 합니다. parent[4] = 3 이라면, 4의 .. 이전 1 ··· 4 5 6 7 8 9 10 ··· 40 다음
