YJLee-devlog 🍎

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

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색칠하기 - BFS //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] //MARK: - Initializer init() { self.edges = [] } ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제에서는 조심해야 하는 부분이 예시 입력에는 오름차순으로 입력이 되지만 계속 오름차순으로 입력 된다는 보장이 없기 때문에 그래프 탐색 전에 인접 리스트를 정렬해주는 작업이 필요함. 5. 전체 코드 //MARK: - 깊이우선탐색과 너비우선탐색 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] //MARK: - Initializer init() { self.edges = [] } } //MARK: - Vairable var graph: [Graph] = [] var visited: [Bool] = [] //MAR..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 그림 1 처럼 입력으로 주어지는 2차원 배열을 그래프라고 가정하고, 현재 원소가 1이라면 상, 하, 좌, 우 방향으로 그래프 탐색(DFS or BFS)을 진행하고, 더이상 상, 하, 좌, 우에 인접한 원소 1이 없다면 탐색을 멈추고 그 때의 count 값을 별도의 배열 혹은 리스트에 저장 이 문제의 경우, 2차원 배열의 입력에 주의해야 하는데, 한 줄 단위로 입력을 받고 있기 때문에, 문자열에 각각의 원소를 정수로 변환하여 배열을 구성해야 함 마지막으로, count 값을 담은 리스트를 정렬하고, 리스트의 크기와 원소를 차례로 출력함으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 단지 번호 붙이기 //MARK: - Framework ..

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 :..