백준 - 늑대와 양 - 16956 - swift

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

16956번: 늑대와 양

 

 

실버 4의 낮은 난이도지만, 재밌는 문제였다.

 

문제 유형은 구현에 가깝다. 또는 bfs로도 풀 수 있긴 하다.

즉 bfs를 몰라도 풀 수 있는 문제다. 

사실 나도 문제를 보자마자 bfs가 딱 떠올랐다. 

대체로 bfs나 dfs가 들어가면 최소 실버1~2의 난이도를 갖는데, 의아했다. 왜 실버 4일까? 

 

처음에는 늑대를 기준으로 bfs를 돌리면서 양을 만나는...이런 생각을 하다가,

양을 기준으로 잡아서, 양의 주변에 . 가 있다면 바로 울타리르 심는 걸로 하고, 더 이상 탐색하지 않고, 

양이 있다면 계속 탐색하고, 늑대가 있다면 안전하지 않다는 걸로 구현했다.

 

풀긴 풀었지만, bfs가 들어가면 코드가 더 길어지는게 어쩔 수 없는데, 다른 분들의 코드들이 대체로 짧은 걸 보고, 

다시 생각했다. 

 

오!  사실 이 문제는 울타리를 최소로 심는게 아니다. 그냥 울타리를 어디든 지어도 늑대가 접근하지 못하면 성공이다. 

 

즉, 그냥 아예 처음부터 . 인 곳은 울타리를 심어버린다. 

그리고 ?

그냥 2차원배열을 돌면서, 늑대인경우에, 좌우 위아래 양이 있는지만 판별하면 된다. 

 

이미 양과 늑대를 제외한 곳은 이미 울타리로 다 쳐져있기때문에, 좌우위아래로 양이 존재한다면 이는 어떤식으로든 늑대가 양을 찾을 수 밖에 없다.

 

ㅎㅎ 재밌는 문제다.

 

 

let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
let row = inp[0], col = inp[1]
var arr = [[String]]()
for _ in 0..<row {
    var l = readLine()!.map{String($0)}
    for j in 0..<col {
        if l[j] == "." {
            l[j] = "D"
        }
    }
    arr.append(l)
}
let dir = [(0,1),(0,-1),(1,0),(-1,0)]
var isSafe = true

for i in 0..<row {
    for j in 0..<col {
        if arr[i][j] != "W" { continue }
        for k in 0..<4 {
            let n = (i+dir[k].0, j+dir[k].1)
            if n.0>=row||n.1>=col||n.0<0||n.1<0{continue}
            if arr[n.0][n.1] == "S" {
                isSafe = false
                break
            }
        }
    }
}

if isSafe {
    print(1)
    arr.forEach {
        print($0.joined())
    }
} else {
    print(0)
}