[Swift] BOJ 2667 단지번호붙이기

BOJ 2667 단지번호붙이기

 

✅ BOJ 2667 단지번호붙이기

이거 하루 반 풀었는데, 논리로는 알겠는데 안되다가 유기농 배추 풀고나서 다시 풀면서 맞음.

 

✅ 알고리즘 접근법

유기농 배추와 유사하나 각 그룹의 갯수를 따로 저장해야하므로 그것만 한번 더 체크하면 된다.

근데 내 알고리즘의 치명적인 문제가 있다.

단독 그룹인지 체크할 수는 있으나, 단독 블럭일 경우 그 블럭이 count를 계산할 수 없다는 점.

그래서 보완을 위해 dx,dy에 0,0을 추가하여 해결하였다.

 

유기농 배추를 먼저 읽어보고 이 문제를 풀면 수월하게 이해할 수 있다.

 

2022.04.03 - [코딩테스트] - [Swift] BOJ 1012 유기농 배추

[Swift] BOJ 1012 유기농 배추

 

✅ 코드

struct b2667{
    static func run() {
        let n = Int(readLine()!)!
        
        var matrix = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
        var visited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
        for i in 0..<n {
            let v = readLine()!.compactMap { $0.wholeNumberValue! } // string을 손쉽게 [Int] 배열로 분리하는 코드
            matrix[i] = v
        }
        
        // 자기자리 + 상하좌우
        let dx = [0, -1, 1, 0, 0]
        let dy = [0, 0, 0, -1, 1]
        
        var queue = [[Int]]()
        var group = 0 // 만들어진 블럭의 갯수
        var count = 0 // 각 블럭의 갯수
        var answer = [Int]()
        
        for i in 0..<n { // 행우선 반복
            for j in 0..<n { // 열우선 반복
                
                if matrix[i][j] == 1 && visited[i][j] == false { // 그 행의 값이 1이고, 방문한 적이 없다면
                    // BFS 알고리즘을 채택함
                    queue.append([i,j]) // queue에 넣는다
                    
                    while !queue.isEmpty { // 큐가 비어있지 않다면 지속적으로 수행.
                        // 큐의 제일 앞의 값을 빼낸다.
                        let x = queue[0][0]
                        let y = queue[0][1]
                        
                        queue.removeFirst()
                        
                        for i in 0..<5 { // 상하좌우를 돈다.
                            // 큐에서 꺼낸 기준값을 기준으로 상하좌우 변수를 하나씩 정해서 탐색한다.
                            let nx = x + dx[i]
                            let ny = y + dy[i]
                            
                            // matrix안에 index가 위치하고, 방문한 적 없는 위치라면
                            if nx >= 0 && ny >= 0 && nx < n && ny < n && visited[nx][ny] == false {
                                
                                if matrix[nx][ny] == 1 { // 그 위치의 값이 1이라면
                                    queue.append([nx, ny])
                                    visited[nx][ny] = true
                                    count += 1
                                }
                            }
                        } // for
                    } // while
                    
                    group += 1 // 만들어진 블럭의 갯수
                    answer.append(count)
                    count = 0
                }
            }
        }
        
        print(group)
        answer = answer.sorted(by: <)
        answer.forEach {
            print($0)
        }
    }
}