[Swift][DFS] 백준 2667번 (단지번호붙이기)

요구능력 : 문제의 조건과 DFS에 대한 이해

 

코드설명 : 

 

문제를 보면 단지를 전부 돌아봐야 할 것 같다.

전부 돌면서 1이 뭉쳐있는곳은 하나의 단지라고 본다.

1이 뭉쳐있는곳을 DFS로 돌려서 모두 탐색해봐야한다.

그렇다면 아직 방문하지 않은곳이면서 1인좌표를 찾아서 dfs를 돌면된다.

for i in 0..<n {
    for j in 0..<n{
        if arr[i][j] == 1 && !visited[i][j] { //1인좌표이면서 방문하지않은곳을 방문
            count = 0
            dfs(i, j)
            result.append(count)
        }
    }
}

 

그리고 탐색알고리즘을 짜려면 우선, 현재 들어온 좌표는 방문한 좌표이다.

처음에 방문처리를 해주고 우리가 탐색할 곳은 좌,우,위,아래이기 때문에 총 4번을 탐색할 것이다.

4번을 탐색하면서 탐색할 좌표로 변경해주기 위해  dx와 dy를 더해준다.

여기서 중요한 조건은 dx와 dy는 배열의 밖으로 나가서는 안된다.

그리고 역시나 좌표로 방문한곳이 1이어야되고 아직 방문처리를 하지 않은 곳 이어야 한다.

위의 조건을 모두 만족했으면 확인된 좌표로 dfs를 통해 이동한다.

이동해서 같은 작업을 반복한다.

func dfs(_ x: Int,_ y: Int){
    count += 1
    visited[x][y] = true
    for i in 0...3{
        let nx = x + dx[i]
        let ny = y + dy[i]
        if nx >= 0 && nx < n && ny >= 0 && ny < n {
            if arr[nx][ny] == 1 && !visited[nx][ny] {
                dfs(nx, ny)
            }
        }
        
    }
}

 

 

후기 : 비슷한류의 문제를 겪어본적이 있는거같은데...뭐더라

let n = Int(String(readLine()!))!
var arr: [[Int]] = [[]]
var visited = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
var count = 0
for _ in 1...n {
    arr.append(readLine()!.map{Int(String($0))!})
}
arr.removeFirst()
func dfs(_ x: Int,_ y: Int){
    count += 1
    visited[x][y] = true
    for i in 0...3{
        let nx = x + dx[i]
        let ny = y + dy[i]
        if nx >= 0 && nx < n && ny >= 0 && ny < n {
            if arr[nx][ny] == 1 && !visited[nx][ny] {
                dfs(nx, ny)
            }
        }
        
    }
}
var result: [Int] = []
for i in 0..<n {
    for j in 0..<n{
        if arr[i][j] == 1 && !visited[i][j] {
            count = 0
            dfs(i, j)
            result.append(count)
        }
    }
}
print(result.count)
result.sort()
print(result.map{String($0)}.joined(separator: "\n"))