[백준](Swift) 2667번 - 단지번호붙이기 (DFS의 가장 기본적인 문제)

💁🏻 문제링크

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

💻 문제 풀이

이런 문제를 만나면, 현재위치에서 위, 아래, 오른쪽, 왼쪽을 살펴보면서 연결이 되어있나? 를 판단해야한다. 

위 그림을 보면, 현재 위치는 (0,0)일때 방향키로 움직일 수 있다. x좌표인 0에다가 dx[2]을 더하고, y에다가 dy[2]을 더해주면, (1,0)으로 한칸 아래로 이동할 것이다. 이처럼 이렇게 "연결된 1을 찾아 무언가를 찾는문제"라면, 이렇게 방향키를 생각해서 문제를 풀면 된다.

지금 문제는 1이 연결되어있는 부분을 '색칠'한다고 생각하면 된다.

문제에서 주어진대로, 1이 연결되어있으면 하나의 단지가 되는 것이다.
나는 dfs를 이용해서 1인 곳을 전부 방문하고, 방문했다면 0으로 바꿔주는 방식을 선택했다.

 

💻 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2667_%EB%8B%A8%EC%A7%80%20%EB%B2%88%ED%98%B8%20%EB%B6%99%EC%9D%B4%EA%B8%B0/main.swift

GitHub - deslog/Algorithm

let n = Int(String(readLine()!))!
var graph = [[Int]]()
var cntList = [Int]()
var cnt = 0
let dx = [-1, 1, 0, 0] //위 아 왼 오
let dy = [0, 0, -1, 1]

for _ in 0..<n {
    graph.append(Array(readLine()!.map{ Int(String($0))! }))
}

func dfs(_ i: Int, _ j: Int) -> Int {
    var deque = [(Int, Int)]()
    deque.append((i, j))
    graph[i][j] = 0 // 방문처리
    cnt = 1
    
    while !deque.isEmpty {
        let tem = deque.removeFirst()
        let x = tem.0
        let y = tem.1
        
        for k in 0..<4 {
            let nx = x + dx[k]
            let ny = y + dy[k]
            
            if nx < 0 || ny < 0 || nx >= n || ny >= n {
                continue
            }
            
            if graph[nx][ny] == 1 {
                graph[nx][ny] = 0
                deque.append((nx, ny))
                cnt += 1
            }
        }
    }
    return cnt
}

for i in 0..<n {
    for j in 0..<n {
        if graph[i][j] == 1 {
            cntList.append(dfs(i,j))
        }
    }
}

print(cntList.count)
cntList.sort()
for i in cntList {
    print(i)
}