단지 번호 붙이기_DFS

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

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

5. 전체 코드

//MARK: - 단지 번호 붙이기

//MARK: - Framework
import Foundation

//MARK: - Variable
var graph: [[Int]] = []
var visited: [[Bool]] = []
var count: Int = 0

//MARK: - Function
func dfs(_ x: Int, _ y: Int) -> Void {
    let dx: [Int] = [-1, 1, 0, 0]
    let dy: [Int] = [0, 0, -1, 1]
    
    visited[x][y] = true
    count += 1
    
    for i in 0..<dx.count {
        let nx: Int = x + dx[i]
        let ny: Int = y + dy[i]
        
        if graph[nx][ny] == 1 && !visited[nx][ny] {
            dfs(nx, ny)
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    var homeCounts: [Int] = []
    graph = Array(repeating: Array(repeating: 0, count: N + 10), count: N + 10)
    visited = Array(repeating: Array(repeating: false, count: N + 10), count: N + 10)
    
    for i in 1...N {
        guard let str: String = readLine() else { return }
        for j in 0..<str.count {
            graph[i][j + 1] = Int("\(str[str.index(str.startIndex, offsetBy: j)])") ?? 0
        }
    }
    
    //MARK: - Process
    for i in 1...N {
        for j in 1...N {
            if graph[i][j] == 1 && !visited[i][j] {
                dfs(i, j)
                homeCounts.append(count)
                count = 0
            }
        }
    }
    homeCounts.sort { $0 < $1 }
    
    //MARK: - Output
    print(homeCounts.count)
    for count in homeCounts {
        print(count)
    }
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.