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

BOJ 2667 단지번호붙이기

 

접근 방식

 

유기농 배추와 같은 연결 요소 문제인데, 그룹 개수뿐 아니라 각 단지에 속한 칸 수까지 세야 함. 이중 for문으로 방문 안 한 1을 찾아 BFS로 한 단지를 훑는 뼈대는 같고, 단지마다 칸 수를 세어 배열에 담는 것만 추가됨.

 

여기서 걸린 부분은 이웃 칸을 볼 때만 count를 올리도록 짜서, 상하좌우에 1이 없는 단독 블럭은 자기 자신이 세어지지 않아 count가 0이 되는 점이었음. dx, dy에 (0,0)을 추가해 시작 칸 자신도 탐색 대상에 넣어 해결함.

 

유기농 배추를 먼저 읽고 이 문제를 풀면 이해가 수월함.

 

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

 

[Swift] BOJ 1012 유기농 배추

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)
        }
    }
}