2667번: 단지번호붙이기

풀이

# 사용해야 하는 알고리즘 = dfs 혹은 bfs (완전탐색)
  : 음식 문제와 마찬가지로 연결된 집을 찾으려면
  : 완전 탐색을 통해서 연결된 모든 집을 찾아야 합니다.

# 문제 풀이 아이디어
  : 지도를 행렬로 저장합니다.
  : 집이 나오면 동서남북 완전탐색하고 (방문체크)
  : 단지 수를 셉니다.

# 의사코드
  1. 지도 입력을 받습니다.
  2. 지도의 모든 좌표를 이중반복문으로 돌면서
    2-1. 집을 만나면 dfs를 실시해서 연결된 집의 갯수를 셉니다.
    2-2. dfs에서 반환된 집의 갯수를 빈 배열에 저장합니다.
  3. 결과물 배열을 오름 차순으로 정렬하고 출력합니다.

# 시간 복잡도
  : 모든 정점을 방문하고 각 정점마다 동서남북 4번의 반복문 실행합니다.
  : 최대 O(4 n**n) = O(n**2)인데 n이 최대 25이기 때문에 안전합니다.

코드

아래 dfs에 대한 자세한 설명은 이 포스팅을 참고해주세요.

// 입력 받기
let N = Int(readLine()!)!

var matrix = [[Int]]()
var check = Array(repeating: Array(repeating: false, count: N), count: N)
for _ in 0..<N {
    let line = readLine()!.map { Int(String($0))! }
    matrix.append(line)
}

// 동서남북 좌표 변화
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]

// 현재 좌표가 valid한 좌표인지
func isValid(r: Int, c: Int) -> Bool {
    return r >= 0 && r < N && c >= 0 && c < N && matrix[r][c] == 1 ? true : false
}

// 방문한 node의 갯수를 반환하는 dfs
func dfs(r: Int, c: Int) -> Int {
    check[r][c] = true
    var cnt = 1
    
    for i in 0..<4 {
        let nr = r + dr[i]
        let nc = c + dc[i]
        if isValid(r: nr, c: nc) && !check[nr][nc] {
            cnt += dfs(r: nr, c: nc)
        }
    }
    
    return cnt
}

// 결과 저장용 배열
var results = [Int]()

// 모든 좌표를 순회하면서 집을 만나면 dfs 실시
for r in 0..<N {
    for c in 0..<N {
        if matrix[r][c] == 1 && !check[r][c] {
            results.append(dfs(r: r, c: c)) //👉 dfs의 값 (= 연결된 집의 갯수)를 배열에 저장
        }
    }
}

// 정답 출력
print(results.count)
results.sorted().forEach { print($0) }