[Swift][BFS] 백준 10026 (적록색약)

요구능력 : BFS

 

코드설명 : 

 

이 문제의 핵심

1) 그림이 몇 개의 구역으로 나눠져있다.

2) 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다.

3) 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다.

 

우리가 구해야하는건 구역의 수이다.

그렇다는건 BFS 또는 DFS 함수를 한 번 호출할 때 인접한부분을 탐색하면서 같은 색상인 경우에 방문처리를 하면된다.

다른 색상인 경우에는 큐에 넣지 않음으로써 탐색을 하지않는다.

 

그렇게 모든 배열의 인덱스를 시작점으로 사용해서 방문처리 안된곳만 탐색할 때, 탐색하는 횟수가 곧 구역의 개수이다.

이미 방문처리된 곳은 횟수에 세어진 구역이기 때문이다.

 

적록색약의 경우 하나의 배열을 더 만들어서 R을 G로 치환하여 똑같이 BFS를 탐색하며 개수를 세주었다.

 

후기 : 문제가 어느정도 쉬운수준이다.

DFS로도 충분히 풀 수 있는 문제이다.

let n = Int(String(readLine()!))!
var arr = [[String]]()
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
var result = [Int]()
for _ in 0..<n{
    let a = readLine()!.map{String($0)}
    arr.append(a)
}
var tempArr = Array(repeating: Array(repeating: "A", count: n), count: n)
for i in 0..<n{
    for j in 0..<n{
        if arr[i][j] == "R"{
            tempArr[i][j] = "G"
        }else{
            tempArr[i][j] = arr[i][j]
        }
    }
}

var visited = Array(repeating: Array(repeating: false, count: 10001), count: 10001)
var count = 0
func bfs(_ x: Int, _ y: Int, _ array: [[String]]){
    var queue = [((Int, Int), String)]() //x, y, ,구역 색상
    
    queue.append(((x, y), array[x][y]))
    
    while !queue.isEmpty{
        let pop = queue.removeFirst()
//        print("x : \(pop.0.0) , ny : \(pop.0.1) , count : \(pop.1)")
        for i in 0..<4{
            let nx = pop.0.0 + dx[i]
            let ny = pop.0.1 + dy[i]
            
            
            if nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] {continue}
            if array[nx][ny] != pop.1 {continue}
            visited[nx][ny] = true
            queue.append(((nx,ny), pop.1))
        }
        
    }
   
}
var firstResult = 0
var secondResult = 0

for i in 0..<n{
    for j in 0..<n{
        if !visited[i][j]{
            bfs(i,j, arr)
            firstResult += 1
        }
    }
}
visited = Array(repeating: Array(repeating: false, count: 10001), count: 10001)
for i in 0..<n{
    for j in 0..<n{
        if !visited[i][j]{
            bfs(i,j, tempArr)
            secondResult += 1
        }
    }
}
print("\(firstResult) \(secondResult)")