[Algorithm] 단지번호붙이기

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/2667

💬 Idea

• DFS를 이용하여 풀이하자.

1. 입력을 2차원 배열로 만든다
2. 방문 좌표 배열을 만든다
3. house 좌표를 for문을 돌며 방문되지 않았고 좌표가 1인 경우, 해당 집의 단지 크기를 구하기 위해 dfs를 수행한다.

<dfs 함수 동작 원리>

1. 상하좌우를 이동하며 깊이탐색을 한다.
   1. 이동 시 count를 1 증가한다.
2. 만약 상하좌우 좌표가 이동할 수 없는 좌표라면 함수를 탈출해준다.

💬 풀이

import Foundation

func solution2667() {
    let N = Int(readLine()!)!
    var houseArr: [[Int]] = []
    
    for _ in 0..<N {
        let house = readLine()!
        houseArr.append(Array(house).map({ Int(String($0))! }))
    }
    
    var visited = Array(repeating: Array(repeating: false, count: houseArr[0].count), count: houseArr.count)
    var count = 0
    
    func dfs(xy: [Int]) {
        let x = xy[0]
        let y = xy[1]
        
        if x < 0 || y < 0 || x > houseArr.count - 1 || y > houseArr[0].count - 1 { return }

        if !visited[x][y] && houseArr[x][y] == 1 {
            visited[x][y] = true
            count += 1
            dfs(xy: [x + 1, y])
            dfs(xy: [x - 1, y])
            dfs(xy: [x, y + 1])
            dfs(xy: [x, y - 1])
        }
    }
    
    var ans: [Int] = []
    
    for (idx, i) in houseArr.enumerated() {
        for (jdx, _) in i.enumerated() {
            if !visited[idx][jdx] && houseArr[idx][jdx] == 1 {
                count = 0
                dfs(xy: [idx, jdx])
                ans.append(count)
            }
        }
    }
    
    print(ans.count)
    for a in ans.sorted() {
        print(a)
    }
}

소요시간 : 20분