Algorithm) BOJ) 백준 2667 - 단지번호붙이기

문제보러가기

2667번: 단지번호붙이기

1. 초기접근

문제 조건 해석

전형적인 DFS 문제이다. (0,0) ~ (n, n) 까지 돌면서 방문하지 않은 곳은 단지를 이룬다.

알고리즘

(0,0) ~ (n,n) 까지 돌면서 아직 방문하지 않았고, 1인 곳에서 dfs 탐색을 시작한다.

이는 새로운 단지가 생겼음을 의미하므로 count를 0으로 초기화하고 dfs 탐색 후에 count값을 저장한다.

dfs 탐색에서는 현재 위치를 방문체크하고 map의 범위 안에서 동서남북을 탐색해나간다.

 

2. 회고

크게 어렵진 않았던 문제지만 입출력 받는 부분에 좀 더 익숙해져야 할 것 같고,

count = 0

dfs(i, j)

result.append(count)

의 로직을 생각하지 못해서 count != 0 일 때의 if 문을 추가해 비효율적인 코드로 작성했었다.

 

3. 코드

func solution() {
    guard let n = readLine().map({Int($0)!}) else {return}
    
    var map = [[Character]](repeating: [Character](), count: n)
    var visited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
    var count = 0
    var result = [Int]()
    var nextRow = [-1, 0, 1, 0]
    var nextCol = [0, 1, 0, -1]
    
    for i in 0..<n {
        let inputs = readLine()!
        for s in inputs {
            map[i].append(s)
        }
    }
    
    func dfs(row currentRow: Int, col currentCol: Int) {
        if visited[currentRow][currentCol] {
            return
        }
        
        visited[currentRow][currentCol] = true
        
        if map[currentRow][currentCol] == "1" {
            count += 1
            for i in 0..<4 {
                let nextR = currentRow + nextRow[i]
                let nextC = currentCol + nextCol[i]
                if nextR >= 0 && nextR < n && nextC >= 0 && nextC < n {
                    dfs(row: nextR, col: nextC)
                }
            }
        }
    }
    
    for i in 0..<n {
        for j in 0..<n {
            if !visited[i][j] && map[i][j] == "1" {
                count = 0
                dfs(row: i, col: j)
                result.append(count)
            }
        }
    }
    
    print(result.count)
    for i in result.sorted(by: <) {
        print(i)
    }
}

solution()