YJLee-devlog 🍎

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 전형적인 그래프 탐색 문제로 DFS or BFS로 문제를 해결할 수 있음 인접한 노드를 방문할 때 마다, count 값을 증가시켜줌으로써 문제를 해결할 수 있고, O(N + M)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 웜 바이러스 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] //MARK: - Initializer init() { self.edges = [] } } //MARK: - Variable var graph: [Graph] = [] var visited: [Bool] =..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 그래프의 같은 집합의 노드에 간선이 존재하는지 판단하기 위해서는 그래프를 하나하나 탐색해 봐야 함 따라서 깊이우선탐색을 통해 노드를 방문하고, 여기서 같은 집합인지 아닌지는 처음부터 알 수 없으므로 노드의 번호마다 그룹(0 혹은 1)을 부여하는 배열을 통해 같은 집합인 것을 확인할 수 있음 노드를 방문할 때, 현재 연결된 노드의 그룹이 1이라면 0을, 0이라면 1을 부여함으로써 집합을 관리할 수 있고, 여기서 같은 집합이라면, 노드끼리 연결되어 있으면 안되기 때문에, 현재노드와 인접한 노드 중에 그룹이 같은 것이 있다면 이분 그래프가 될 수 없음. 따라서 O(N + M)의 시간복잡도로 문제를 해결 5. 전체 코드 //MARK: - 이분 그래프 판별..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 인접리스트로 그래프를 구현하고, 깊이 우선 탐색을 진행하면서 각 노드를 방문할 때마다 인접한 노드의 색이 0이라면 1, 1이라면 0을 칠함 인접한 노드들에 대한 색칠을 마치고, 현재노드와 인접한 노드 중 같은 색이 있으면 2색 색칠하기가 불가능한 것을 알 수 있음 따라서 O(N + M)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 2색칠하기 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] //MARK: - Initializer init() { self.edges = [] } } //MA..

1. 문제 그래프 자료구조를 인접 리스트로 구현 2. 문제 설계 그래프를 인접 리스트로 구현하게 되면, 두 정점이 연결돼 있는지 여부를 O(1)만에 알 수 있는 인접 행렬에 비해 O(차수) 만큼 걸리게 되므로, 이 부분이 단점이 될 수 있음 하지만, 인접 행렬에 비해 공간 활용도가 높으며, 연결되어 있는 모든 정점의 개수를 파악하는데 인접 행렬보다 효율적이게 파악할 수 있음 3. 전체 코드 //MARK: - 그래프 구현 : 인접 리스트 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] //MARK: - Initializer init() { self.edges = [] }..

1. 문제 그래프 자료구조를 인접 행렬로 구현 2. 문제 설계 그래프를 인접 행렬로 구현하게 되면, 두 정점이 연결돼 있는지 여부를 O(1)만에 알 수 있음 하지만, 무조건 정점의 개수의 제곱개 만큼의 2차원 배열로 불필요한 공간이 발생할 수 있으며 특정 정점과 연결된 모든 정점을 구하는데 O(정점의 개수)만큼 걸리게 됨 3. 전체 코드 //MARK: - 그래프 구현 : 인접 행렬 //MARK: - Framework import Foundation //MARK: - Function func isConnected(_ myGraph: [[Int]], _ x: Int, _ y: Int) -> Bool { //Time Complexity : O(1) return myGraph[x][y] == 1 ? true :..