단지 번호 붙이기_BFS

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

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

5. 전체 코드

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

//MARK: - Framework
import Foundation

//MARK: - Type
struct Node {
    //MARK: - Property
    var x, y: Int
    
    //MARK: - Initializer
    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }
}

//MARK: - Variable
var graph: [[Int]] = []
var visited: [[Bool]] = []
var dx: [Int] = [-1, 1, 0, 0]
var dy: [Int] = [0, 0, -1, 1]

//MARK: - Function
func bfs(_ x: Int, _ y: Int) -> Int {
    var result: Int = 1
    var queue: [Node] = []
    queue.append(Node(x, y))
    visited[x][y] = true
    
    while !queue.isEmpty {
        let currentNode: Node = queue.removeFirst()
        
        for i in 0..<4 {
            let nx: Int = currentNode.x + dx[i]
            let ny: Int = currentNode.y + dy[i]
            
            if !visited[nx][ny] && graph[nx][ny] == 1 {
                visited[nx][ny] = true
                queue.append(Node(nx, ny))
                result += 1
            }
        }
    }
    
    return result
}

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 data: String = readLine() else { return }
        for j in 1...N {
            graph[i][j] = Int("\(data[data.index(data.startIndex, offsetBy: j - 1)])")!
        }
    }
    
    //MARK: - Process
    for i in 1...N {
        for j in 1...N {
            if graph[i][j] == 1 && !visited[i][j] {
                homeCounts.append(bfs(i, j))
            }
        }
    }
    
    homeCounts.sort { $0 < $1 }
    
    //MARK: - Output
    print(homeCounts.count)
    for count in homeCounts {
        print(count)
    }
}
solution()

 

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