백준 1303 DFS 활용문제

WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

W와 붙어있는 W들의 총합 = 9 , 7

W 의 위력은 81 + 49 = 130 이다.

 

결국 붙어있는 W들의 총 합을 구한다면 되는 문제이다.

어떻게 구할수 있을까?

 

DFS 를 통해 가능하다.

첫번째 (0,0) 에있는 W를 보자.

오른쪽엔 B 아래엔 W가있다. (위 왼쪽은 비어있으니 패스)

그럼 아래에 있는 W는 붙어있기 때문에 위력에 도움이될것이다.

 

이제 아래에있는 W 의 근처를 보고 또 W가있다면

또 그 W에 붙어있는 W가있다면 계속해서 합을 구해서 인접한 W의 갯수를 구하면 된다.

그렇게 위쪽에 있는 W무리를 구할수있다.

이게 지금 딱 한번 dfs를 돌린것이다.

 

dfs는 0,0 부터 5,5까지 반복해야한다.

그러기위해서는 2차원배열을 반복해야하며

 

visited를 사용해서 이미 확인 한것은 skip 할수있다.

visited도 역시 2차원 배열 이어야한다.

C = checked(이미 체크한거)

CBCCC
CCCCC
BBBBB
BBBWW
WWWWW

func solution(char:String,arr:[[String]],visited: inout [[Int]]) -> Int{
    var sum = 0
    for m in 0..<arr.count{
        
        for n in 0..<arr[m].count{
            var dfsSum = 0

            dfs(n: n, m: m, visited: &visited, arr: arr, char: char, sum: &dfsSum)
            sum += dfsSum * dfsSum
        }
    }
    return sum
}

let w = solution(char: "W", arr: arr, visited: &visited)
let b = solution(char: "B", arr: arr, visited: &visited)

print("\\(w) \\(b)")

dfs 함수에서 예외적인 상황이있다.

 

1. 우선 지금 탐색하려는 위치가 이차원 배열을 초과하지 않았는지 체크

ex> 5 x 5 배열인데 5,6번째값을 찾는다)

 

2. visited 체크 (이미 방문한건지)

3. 찾으려는 알파벳인 경우만 로직 실행

 

 

 

 

모두 통과 했다면 이제 인접한 모든 위치들을 dfs 돌릴건데

정상적인 경우 동서남북 총 4개를 체크해야한다.

2,2 -> 2-1,2 / 2+1,2 / 2,2+1 / 2,2-1

그러나 만약 n 이나 m 이 0인경우 예외가있다.

0,0 -> 0,0+1 / 0+1,0
1,0 -> 1-1,0 / 1+1,0 / 1,0+1

func dfs(n:Int,m:Int,visited: inout [[Int]],arr:  [[String]],char:String,sum: inout Int){
    if(n>=arr[0].count || m>=arr.count) { return }
    if(visited[m][n] == 1){ return }

    if(arr[m][n] == char){
        visited[m][n] = 1

        sum += 1
        if(n == 0){
            dfs(n: n+1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
        }else{
            dfs(n: n-1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
            dfs(n: n+1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
        }
        if(m == 0){
            dfs(n: n, m: m+1, visited: &visited, arr: arr,char:char,sum:&sum)
        }else{
            dfs(n: n, m: m-1, visited: &visited, arr: arr,char:char,sum:&sum)
            dfs(n: n, m: m+1, visited: &visited, arr: arr,char:char,sum:&sum)
        }
    }
}

전체 코드

func solution(char:String,arr:[[String]],visited: inout [[Int]]) -> Int{
    var sum = 0
    for m in 0..<arr.count{
        
        for n in 0..<arr[m].count{
            var dfsSum = 0

            dfs(n: n, m: m, visited: &visited, arr: arr, char: char, sum: &dfsSum)
            sum += dfsSum * dfsSum
        }
    }
    return sum
}

func dfs(n:Int,m:Int,visited: inout [[Int]],arr:  [[String]],char:String,sum: inout Int){
    if(n>=arr[0].count || m>=arr.count) { return }
    if(visited[m][n] == 1){ return }

    if(arr[m][n] == char){
        visited[m][n] = 1

        sum += 1
        if(n == 0){
            dfs(n: n+1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
        }else{
            dfs(n: n-1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
            dfs(n: n+1, m: m, visited: &visited, arr: arr,char:char,sum:&sum)
        }
        if(m == 0){
            dfs(n: n, m: m+1, visited: &visited, arr: arr,char:char,sum:&sum)
        }else{
            dfs(n: n, m: m-1, visited: &visited, arr: arr,char:char,sum:&sum)
            dfs(n: n, m: m+1, visited: &visited, arr: arr,char:char,sum:&sum)
        }
    }
}

var lengthInput = readLine()!.split(separator: " ").map{Int($0)!}
var n = lengthInput[0]
var m = lengthInput[1]
var arr = [[String]]()
for _ in 0..<m{
    let temp = Array(readLine()!).map{String($0)}
    arr.append(temp)
}

var visited = Array(repeating: Array(repeating: 0, count: n), count: m)

let w = solution(char: "W", arr: arr, visited: &visited)
let b = solution(char: "B", arr: arr, visited: &visited)

print("\\(w) \\(b)")