[Swift] BOJ 1012 유기농 배추

BOJ 1012 유기농 배추

 

✅ 오 일단 문제 이름이 정말 맘에 든다.

각설하고, 알고리즘은 한번에 확 떠올렸는데, 이 논리가 다른 문제에 코드로 구현하다가 막혀서 그 문제를 건너 뛰고 하다가 그냥 다시 도전해봄.

 

일단 풀긴 풀었는데 시간은 1시간 걸림.

이유는 count를 처리해야 하는 부분이 내 논리상 while을 탈출한다면 queue가 비면서 하나의 블럭(그룹)이 만들어졌다는 말로 이해하는데, 근데 visited 처리 부분에서 좀 꼬인게 있었나봄.

 

풀었으니까 이번 문제는 리뷰가 절대적으로 필요할 것 같아서 리뷰함.

 

✅ 알고리즘 접근법.우선 미로 찾기 문제와 다르게 얘는 어디가 시작 포인트가 되는지 알 수가 없음.그래서 이중 for문을 돌면서 1이 어디있는지 찾고자 함.그리고 1을 찾으면 그 위치에서 BFS를 수행하여 그룹을 만들고자 했음.

 

while을 탈출한다는 의미는 즉, BFS를 적용하여  상하좌우를 다 탐색했을 때,이동할 장소가 없다는 더이상 없다는 말임.

이동할 장소가 없으므로, 카운트를 하나 올린다.

그리고 다시 이중 for문을 돌면서 1의 위치를 찾는다.

여기서 이미 만들어진 블럭에 속한 1이면 visited를 true로 처리를 해두어서 계산을 다시하는 것을 막는다.

 

✅ 코드

제출할 때는 run메소드 안에 있는 코드만 제출하면 됩니다. 

주석 잘 달아 두어서 흐름 따라가면서 꼭 다시보자!!!!

//https://www.acmicpc.net/problem/1012
import Foundation

struct b1012 {
    static func run() {
        // Input 처리
        let n = Int(readLine()!)!
        var answer = [Int]()
        
        for _ in 0..<n { // 여러개의 테스트 케이스를 수행해야 하므로 for문으로 반복 횟수를 정한다.
            let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            
            var matrix = [[Int]](repeating: [Int](repeating: 0, count: input[1]), count: input[0])
            var visited = [[Bool]](repeating: [Bool](repeating: false, count: input[1]), count: input[0])
            
            for _ in 0..<input[2] {
                let line = readLine()!.split(separator: " ").map{ Int(String($0))! }
                matrix[line[0]][line[1]] = 1
            }
            
            // 상하좌우
            let dx = [-1, 1, 0, 0]
            let dy = [0, 0, -1, 1]
            
            var queue = [[Int]]()
            var count = 0 // 한 테스트 케이스의 결과값을 저장하는 변수
            
            for i in 0..<input[0] { // 행우선 반복
                for j in 0..<input[1] { // 열우선 반복
                    
                    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..<4 { // 상하좌우를 돈다.
                                // 큐에서 꺼낸 기준값을 기준으로 상하좌우 변수를 하나씩 정해서 탐색한다.
                                let nx = x + dx[i]
                                let ny = y + dy[i]
                                
                                // matrix안에 index가 위치하고, 방문한 적 없는 위치라면
                                if nx >= 0 && ny >= 0 && nx < input[0] && ny < input[1] && visited[nx][ny] == false {
                                    
                                    if matrix[nx][ny] == 1 { // 그 위치의 값이 1이라면
                                        queue.append([nx, ny]) // 큐에 넣고
                                        visited[nx][ny] = true // 값이 1인 여기는 방문했다고 처리
                                        /* (주의)
                                         모든 곳을 visited처리하지 않고 1로 정해진 위치를 방문했는지만 확인하면 되므로
                                         1인 위치가 방문했는지 안했는지만 체크함.
                                         */
                                    }
                                }
                            } // for
                        } // while
                        
                        count += 1 // while문을 탈출했다는 건, 연속적으로 이어지지 않아 하나의 블럭이 만들어졌다는 의미이므로 이때 카운팅
                    }
                }
            }
            answer.append(count)
        }
        answer.forEach {
            print($0)
        }
    }
}