백준 16956 늑대와 양, 실버문제 애드혹 알고리즘 swift 풀이

 

 

---

백준 16956, 늑대와 양 문제 개요, 애드혹(ad-hoc)이란?

오늘은 백준 16956, 늑대왕 양 문제를 풀어보겠습니다. 해당 문제는 애드혹 문제로, 애드혹이란 특정 접근방법 없이 창의적 아이디어를 활용해서 풀 수 있는 문제라고 합니다. 실버3 티어의 문제로, 늑대에게 양이 잡아먹히지 않도록 울타리를 놓을 수 있다면 1과 그래프 상태를, 늑대에게 잡하먹힐 수밖에 없다면 0을 출력하는 문제입니다.

해당 문제의 중요한 점은 울타리를 놓는데 제한이 없다는 것입니다. 몇개의 울타릴 놓던간에, 양이 먹히지만 않으면 됩니다. 그렇게 제가 생각한 것은 "모든 양과 늑대가 처음에 붙어있지만 않는다면 무조건 양이 울타리를 놓아 살 수 있다" 입니다. 그리고, "양이 살기 위해 최대한 자신의 주변의 빈공간에 울타리를 놓으면 살 수 있다." 입니다. 이를 swift코드로 구현해보겠습니다.

 

 

---

백준 16956, 늑대와 양 문제 swift 풀이

평소에 커스텀으로 만들어 쓰던 클로져를 그대로 사용했습니다. 입력량이 적은 문제라 그냥 split이나 components 활용하셔도 문제 없습니다. R, C로 행과 열을 입력받고, G 그래프를 그려주었습니다.

 

 

입력받은 그래프를 다시 순회합니다. "S" 양일 경우에 대해서만 체크합니다. 양일 경우 인접한 늑대가 존재한다면 양은 먹힐수밖에 없으므로 즉시, 0을 출력합니다. 만약 인접공간에 자리가 비면, 울타리를 무조건 설치해서 양이 늑대에게 먹히지 않도록 해줍니다. 그렇게 모든 순회를 거쳤을때 양이 늑대와 인접하는 경우가 없다면, 양은 무조건 살 수 있습니다. 당당하게 1을 반환해줍니다.

 

 

 

양이 살수 없으면 0을 출력, 양이 살 수 있으면 울타리르 놓았던 그래프 G를 주어진 포맷에 맞게 출력해줍니다. 저는 reduce와 joined를 활용해서 [[Character]] 타입의 그래프, G를 주어진 포맷에 맞게 String 타입으로 변화해서 출력해주었습니다.

 

 

---

이렇게 간단하게 늑대와 양 에드혹(ad-hoc) 알고리즘 문제를 풀어보았습니다. swift언어 풀이 제출 결과는 아래와 같습니다. 이만 포스팅 마치겠습니다. 즐거운 코딩 되세요.

 

 

 

---

백준 16956, 늑대와 양 swift언어 제출 결과

 

 

 

---

백준 16956, 늑대와 양 swift언어 전체 소스코드 

let readInput: (() -> [Int]) = {
    var result: [Int] = []
    var temp = 0
    readLine()!.forEach { char in
        if char == " " {
            result.append(temp)
            temp = 0
            return
        }
        
        temp = temp * 10 + Int(char.asciiValue!) - 48
    }
    result.append(temp)
    return result
}

let ip = readInput()
let (R, C) = (ip[0], ip[1])
var G: [[Character]] = []
(0..<R).forEach { _ in
    G.append(Array(readLine()!))
}

let dx = [0, 0, -1, 1]
let dy = [1, -1, 0, 0]

func canSaveSheeps() -> Int {
    for idx in G.indices {
        for jdx in G[idx].indices {
            if G[idx][jdx] != "S" { continue }
            for ddx in dx.indices {
                let nx = idx + dx[ddx]
                let ny = jdx + dy[ddx]
                if nx < 0 || ny < 0 || nx >= R || ny >= C || G[nx][ny] == "S" { continue }
                if G[nx][ny] == "W" { return 0 }
                G[nx][ny] = "D"
            }
        }
    }
    return 1
}

if canSaveSheeps() == 0 {
    print(0)
} else {
    print(G.reduce(into: ["1"]) { rowList, row in
        rowList.append(row.map { "\($0)" }.joined())
    }.joined(separator: "\n"))
}