YJLee-devlog 🍎

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

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 가중치가 없는 그래프에서 최단 거리를 찾기 위해서는 그래프 탐색 알고리즘 중 BFS 알고리즘이 적절함 DFS도 최단거리를 찾을 수는 있지만, 깊이우선탐색은 계속 해서 낮은 레벨로 탐색하므로 적절하지 않음 인접한 노드들부터 차례로 방문하는 너비우선탐색으로 방문할 때마다 거리를 이전 노드의 거리에 + 1 씩 누적시키고, 마지막으로 목적지의 거리를 출력함으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 미로 찾기 //MARK: - Framework import Foundation //MARK: - Type struct Node { //MARK: - Property var x, y: Int //MARK: - Initializer init(_..

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