문제 링크

백준 1012: 유기농 배추

문제 분석

  • 배추밭에서 연결된 배추 그룹의 개수를 구하는 문제
  • 각 연결된 그룹마다 지렁이 1마리씩 필요
  • 상하좌우로 인접한 배추들은 같은 그룹

=>

**Connected Components 개수 구하기 문제!

  • 각 배추에서 시작해서 연결된 모든 배추를 탐색하면 되는 문제로, 이 때 주의할 점은 한 번 방문한 배추는 다시 방문하지 않아야 함.

  • 이 문제는 DFS, BFS 모두 가능하나, 최단 거리가 아닌 ‘연결성만 확인하면 되는’ 문제로 DFS 가 적합함.

  • 각 칸을 최대 한 번씩은 방문하므로, O(M x N)의 시간복잡도를 가짐. (배추가 k개라고 해도, 전체 격자를 확인해야 함.)

  • 최대 50x50 이므로 스택 오버플로우 위험 낮음

배운 점

코딩테스트 문제를 풀 때는 최대한 전역변수를 사용해서, 간단하게 풀려고 했으나 Swift로 풀면


38 | 
39 | func dfs(_ y: Int, _ x: Int) {
   |      `- note: add '@MainActor' to make global function 'dfs' part of global actor 'MainActor'
40 |     visited[y][x] = 1

위와 같은 문제가 빈번하게 발생함.

처음 코드


import Foundation
// connected components 문제!

var t = Int(readLine()!)!

var arr: [[Int]] = []
var visited: [[Int]] = []
var cnt = 0

let dy = [-1, 0, 1, 0]
let dx = [0, 1, 0, -1]
var (n, m, k) = (0, 0, 0)

while t > 0 {
    // 가로: n, 세로: m, 배추 위치 개수: k
    let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
    (n, m, k) = (input[0], input[1], input[2])

    arr = Array(repeating: Array(repeating: 0, count: m), count: n)
    visited = Array(repeating: Array(repeating: 0, count: m), count: n)

    for i in 0..<k {
        let s = readLine()!.components(separatedBy: " ").map { Int($0)! }
        arr[s[0]][s[1]] = 1 // 배추 위치 입력
    }

    for i in 0..<n {
        for j in 0..<m {
            // 아직 방문하지 않았고, 배추가 심어져있는 곳이라면 dfs
            if visited[i][j] == 0 && arr[i][j] == 1 {
                dfs(i, j, &arr, &visited)
                cnt += 1
            }
        }
    }
    t -= 1
}

func dfs( y: Int,  x: Int, arr: [[Int]], visited: inout [[Int]]) {
    visited[y][x] = 1

    for i in 0..<4 {
        let ny = y + dy[i]
        let nx = x + dx[i]

        if ny < 0 || ny >= n || nx < 0 || nx >= m { continue }
        if visited[ny][nx] == 0 && arr[ny][nx] == 1 { 
            dfs(ny, nx)
        }  
    }
}

print(cnt)

cnt 초기화를 누락, 매개변수를 누락하거나, print 위치를 잘못설정하는 작은 실수들이 있었음.

리팩토링 코드

import Foundation
// connected components 문제!

// 전역 변수
let t = Int(readLine()!)!
let dy = [-1, 0, 1, 0]
let dx = [0, 1, 0, -1]

func dfs(_ y: Int, _ x: Int, arr: [[Int]], visited: inout [[Int]], _ n: Int, _ m: Int) {
    visited[y][x] = 1

    for i in 0..<4 {
        let ny = y + dy[i]
        let nx = x + dx[i]

        if ny < 0 || ny >= n || nx < 0 || nx >= m { continue }
        if visited[ny][nx] == 0 && arr[ny][nx] == 1 { 
            dfs(ny, nx, arr, &visited, n, m)
        }  
    }
}

// arr, n, m, visited 는 테스트 케이스마다 초기화를 시켜야 하는 것에 유의해야 함.

for _ in 0..<t {
    let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let (n, m, k) = (input[0], input[1], input[2])

    var arr = Array(repeating: Array(repeating: 0, count: m), count: n)
    var visited = Array(repeating: Array(repeating: 0, count: m), count: n)
    var cnt = 0  // 각 테스트케이스마다 초기화

    for _ in 0..<k {
        let pos = readLine()!.components(separatedBy: " ").map { Int($0)! }
        arr[pos[0]][pos[1]] = 1
    }

    for i in 0..<n {
        for j in 0..<m {
            if visited[i][j] == 0 && arr[i][j] == 1 {
                dfs(i, j, arr, &visited, n, m)
                cnt += 1
            }
        }
    }

    print(cnt)
}

정리

arr, n, m, visited 등 테스트 케이스마다 초기화를 시켜야 하는 것에 유의해야 함.

inout를 사용하여 함수 내에서 원본 변수를 직접 수정. & 연산자를 사용하여 이 변수의 메모리 주소를 함수에 전달함. 함수가 원본에 직접 접근할 수 있게 해줌.