[Swift 백준] 음식물 피하기

풀이 아이디어

• 그래프 탐색문제입니다.
• 저는 기본적으로 bfs를 더 선호해서 bfs로 풀이합니다.
• 문제 설명이 조금 부실하지만, 결국 색깔이 다른 타일의 크기를 구하는 문제와 같은 맥락입니다.
• 쓰레기가 있는 타일을 1, 없는 타일을 0으로 지정하고 풀이합니다.

자세한 설명은 코드를 참고해주세요

풀이

let nmk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m, k) = (nmk[0], nmk[1], nmk[2])

var dm = [0, 0, -1, 1]
var dn = [-1, 1, 0, 0]

var isVisited = Array(repeating: Array(repeating: 0, count: m), count: n)

for _ in 0..<k {
    let rc = readLine()!.split(separator: " ").map { Int($0)! }
    let (r, c) = (rc[0] - 1, rc[1] - 1)
    isVisited[r][c] = 1
}

var resultArr = [Int]()

func bfs(startM: Int, startN: Int) {
    var queue = [[startM, startN]]
    var count = 0

    while !queue.isEmpty {
        let current = queue.removeFirst()
        let currentM = current[0]
        let currentN = current[1]

        // 조건 필터링 필요, 없으면 시간 초과 남
        if isVisited[currentN][currentM] == 0 { continue }
        isVisited[currentN][currentM] = 0
        count += 1

        for i in 0..<4 {
            let nextM = currentM + dm[i]
            let nextN = currentN + dn[i]

            if nextM < m, nextM >= 0, nextN < n, nextN >= 0 {
                if isVisited[nextN][nextM] == 1 {
                    queue.append([nextM, nextN])
                }
            }
        }
    }
    resultArr.append(count)
}

for i in 0..<n {
    for j in 0..<m {
        if isVisited[i][j] == 1 {
            bfs(startM: j, startN: i)
        }
    }
}

print(resultArr.max()!)