[Swift 알고리즘] 백준 11724 연결 요소의 개수

안녕하세요 코코종입니다. 오늘도 dfs입니닷

근데 isVisited에 대한 처리를 했어서 틀렸었는데... 시간초과가 나더라구요 ㅜㅜ 아직은 언제 visited 처리를 하는게 도움이 되는지 잘 모르겠네요... 많이 풀어보죠 뭐 ㅎㅎ

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/20.
//

import Foundation
// 백준 1743 음식물 피하기

let input = readLine()!.split(separator: " ").map { Int(String($0)) ?? 0 }
let n = input[0]
let m = input[1] // n행 m열
let k = input[2]

var board: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n) // 빈곳은 0, 쓰레기가 있는곳은 -1로 하자!

for _ in 0..<k {
    let line = readLine()!.split(separator: " ").map { Int(String($0)) ?? 0 }
    board[line[0] - 1][line[1] - 1] = -1
}

var cnt = 0
var answer = 0 // 가장 큰 쓰레기의 크기

func dfs(r: Int, c: Int) { // cnt: 연속된 쓰레기의 크기
    if board[r][c] == -1 {
        let dr = [-1, 0, 1, 0]
        let dc = [0, 1, 0, -1]
        
        for d in 0..<4 {
            let rr = r + dr[d]
            let cc = c + dc[d]
            
            if rr >= 0, rr <= n-1, cc >= 0, cc <= m-1 {
                board[r][c] = 0
                dfs(r: rr, c: cc)
            }
        }
        cnt += 1
//        return
    }
//    return
    
}

for r in 0..<n {
    for c in 0..<m {
        cnt = 0 // 초기화
        if board[r][c] == -1 { 
            dfs(r: r, c: c)
            answer = max(answer, cnt)
        }
    }
}

print(answer)

어느정도 구현은 다했는데 board[r][c] = 0으로 처리해주는 방식에 대해서는 어려웠네용..ㅜ

--> 생각해보니 연결되었던 쓰레기를 모두 0으로 만들어주어야 [r][c]에서 찾을때 중복해서 탐색하지 않겠네요!! 계속 생각하다가 깨달았네요 ㅎㅎ

dfs로 제일 깊이 들어간 다음에 나오면서 cnt += 1를 해주는 방식으로 생각하니까 이해가 잘 되네용 ㅎㅎ