1012 유기농 배추

Today 1/15

유기농 배추 (My Code)

func movingCabbage(_ field: inout [[Int]], _ x: Int, _ y: Int, _ maxX: Int, _ maxY: Int) {
    field[x][y] = 0
    if x-1 >= 0 {
        if field[x-1][y] == 1 {
            movingCabbage(&field, x-1, y, maxX, maxY)
        }
    }
    if y-1 >= 0 {
        if field[x][y-1] == 1 {
            movingCabbage(&field, x, y-1, maxX, maxY)
        }
    }
    if x+1 <= maxX-1 {
        if field[x+1][y] == 1 {
            movingCabbage(&field, x+1, y, maxX, maxY)
        }
    }
    if y+1 <= maxY-1 {
        if field[x][y+1] == 1 {
            movingCabbage(&field, x, y+1, maxX, maxY)
        }
    }
}

for _ in 0..<Int(readLine()!)! {
    let MNK = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (M,N,K) = (MNK[0], MNK[1], MNK[2])
    var field = Array(repeating: Array(repeating: 0, count: M), count: N)
    var earthwormCount = 0
    for _ in 0..<K {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        field[input[1]][input[0]] = 1
    }
    
    for row in 0..<N {
        for col in 0..<M {
            if field[row][col] == 1 {
                earthwormCount += 1
                movingCabbage(&field, row, col, N, M)
            }
        }
    }
    print(earthwormCount)
}

인접한 배추를 탐색해야하는 DFS,BFS 문제이다. 어떤 방식으로 하던 상관은 없을 것 같아서 DFS 재귀를 한 번도 사용을 안해본 것 같아서 재귀를 사용해서 풀어보기로 했다.

유기농 배추 (Others Code)

let T = Int(String(readLine()!))!
let dx: [Int] = [1, 0, -1, 0]
let dy: [Int] = [0, 1, 0, -1]

for _ in 0..<T {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (M, N, K) = (input[0], input[1], input[2])
    var arr = Array(repeating: Array(repeating: 0, count: M+2), count: N+2)
    for _ in 0..<K {
        let XY = readLine()!.split(separator: " ").map { Int(String($0))! }
        arr[XY[1]][XY[0]] = 1
    }
    
    var answer = 0
    var visited = Array(repeating: Array(repeating: false, count: M+2), count: N+2)
    
    for i in 0..<N {
        for j in 0..<M {
            if arr[i][j] == 0 || visited[i][j] { continue }
            answer += 1
            visited[i][j] = true
            
            var queue: [[Int]] = []
            queue.append([i, j])
            
            while !queue.isEmpty {
                let cur: [Int] = queue.removeFirst()
                for i in 0..<4 {
                    let nx = cur[0] + dx[i]
                    let ny = cur[1] + dy[i]
                    if nx < 0 || nx >= N || ny < 0 || ny >= M { continue }
                    if visited[nx][ny] || arr[nx][ny] != 1 { continue }
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }
            }
            
        }
    }
    
    print(answer)
}

다른 해답들을 보니 dx,dy로 상하좌우 경우의 수를 배열로 설정하고, 반복문을 돌려서 범위를 벗어날 경우 continue를 하는 방식으로 많이 푸신 것 같다.

또한 배열을 직접적으로 바꾸지 않고, visited를 사용해서 체크를 하는데, 이 문제의 경우에는 그럴 필요까지는 없을 것 같아서 다음 DFS,BFS가 나오면 참고해서 풀어봐야겠다.