문제 링크 (opens new window)

풀이

1. DFS로 연결된 컴포넌트 크기를 출력하는 문제
2. 보통 연결된 컴포넌트 크기를 구할때 초기 return값을 1로 설정하는 경우가 많은데, DFS는 모든 위치 탐색을 기반으로 하기 때문에 adj[hereY][hereX]로 초기값을 설정해야 한다.
3. 맥스 함수를 매번 호출하며 최종 리턴되는 값을 출력한다.

import Foundation

let NMK = readLine()!.split(separator: " ").map { Int($0)! }; let N = NMK[0]; let M = NMK[1]; let K = NMK[2]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: M+1), count: N+1)
var visited:[[Bool]] = .init(repeating: .init(repeating: false, count: M+1), count: N+1)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]


for _ in 0..<K {
    let coord = readLine()!.split(separator: " ").map { Int($0)! }
    adj[coord[0]][coord[1]] = 1
}

func dfs(_ y: Int, _ x: Int) -> Int {
    var ret = adj[y][x]
    visited[y][x] = true
    for i in 0..<4 {
        let ny = dy[i] + y
        let nx = dx[i] + x

        if ny < 1 || nx < 1 || ny > N || nx > M || visited[ny][nx] || adj[ny][nx] == 0 {
            continue
        }

        ret += dfs(ny, nx)
    }
    return ret
}
var result = Int.min

for i in 1...N {
    for j in 1...M {
        if visited[i][j] { continue }
        result = max(result, dfs(i, j))
    }
}

print(result)