백준 3184번 Swift 알고리즘 연습 - 양_BFS

요즘 계속 알고리즘 스터디를 진행하며 문제를 풀고 있는데...

평소보다 푸는 양이 늘고 면접 + iOS 개발 공부까지 하다보니 도저히 블로그에 기록을 남기기가 쉽지 않다..!

그래도 내가 푸는 몇몇 문제들이 Swift로 블로깅 되어 있지 않은 것을 보고, 그런 문제들 위주로 최대한 기록을 남겨봐야겠다는 생각이 들었다.

 

 이 문제는 전형적인 BFS 문제이다. 정해진 형태의 공간 내에 한칸씩 이동하면서 양과 늑대의 개수를 비교해주면 된다.

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 우선 입력받은 값들을 전부 2차원 배열에 세팅해준다.
2. visit 배열을 만들어 내가 확인하고 지나간 곳인지 아닌지를 표시해준다.
3. 수직과 수평으로만 이동할 수 있다고 하였으므로 dx, dy를 활용하여 이동 가능 범위를 제한한다.
4. 2차원 배열을 setting하는 과정에서 현재 총 양 & 늑대가 몇마리인지 확인한다.
5. 양 혹은 늑대가 없는 비어있는 공간은 확인할 필요가 없으므로, 양 혹은 늑대가 있고 아직 방문하지 않은 지역이라면(visit == 0) 들러서 visit 상태를 1로 변경하고 bfs 함수를 시작하여 그 주변의 값들을 전부 확인한다.
6. bfs 함수는 현재 받은 위치 정보를 바탕으로 동서남북 이동을 한다. 이때 #이 아닌 지역만 움직일 수 있고 이렇게 움직이면서 양 혹은 늑대를 만나게 되면 각각 숫자를 카운팅해준다.
7. 카운팅이 끝나고 비교했을 때 늑대가 양보다 같거나 많으면 전부 늑대, 반대의 경우 양으로 값을 바꿔준다.
8. 이 값을 바탕으로 처음 저장해놓은 양 혹은 늑대의 수를 줄여준다.

 

 

* 3184번

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let r = input[0]
let c = input[1]

var space = [[Character]]()
var visit = [[Int]](repeating: [Int](repeating: 0, count: c), count: r)
var sheep = 0
var wolf = 0
var dx = [1, -1, 0, 0]
var dy = [0, 0, -1, 1]

for _ in 0..<r {
    let setting = Array(readLine()!)

    for j in 0..<c {
        if setting[j] == "o" { sheep += 1 }
        if setting[j] == "v" { wolf += 1 }
    }
    space.append(setting)
}

for i in 0..<r {
    for j in 0..<c {
        if (space[i][j] == "o" || space[i][j] == "v") && visit[i][j] == 0 {
            visit[i][j] = 1
            bfs(i, j, space: &space, visit: &visit, sheep: &sheep, wolf: &wolf)
        }
    }
}

print("\(sheep) \(wolf)")

func bfs(_ x: Int, _ y: Int, space: inout [[Character]], visit: inout [[Int]], sheep: inout Int, wolf: inout Int) {
    var move = [[x, y]]
    var sameSpaceSheep = 0
    var sameSpaceWolf = 0

    if space[x][y] == "o" { sameSpaceSheep += 1 }
    else if space[x][y] == "v" { sameSpaceWolf += 1 }

    while !move.isEmpty {
        let curr = move.removeFirst()
        let x = curr[0]
        let y = curr[1]

        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx >= 0 && nx < space.count && ny >= 0 && ny < space[0].count && visit[nx][ny] == 0 && space[nx][ny] != "#" {
                if space[nx][ny] == "o" { sameSpaceSheep += 1 }
                if space[nx][ny] == "v" { sameSpaceWolf += 1 }
                visit[nx][ny] = 1
                move.append([nx, ny])
            }
        }
    }

    if sameSpaceSheep > 0 && sameSpaceWolf > 0 {
        if sameSpaceSheep > sameSpaceWolf { wolf -= sameSpaceWolf }
        else { sheep -= sameSpaceSheep }
    }
}

 

 

정리(Today I Learned)

1. BFS 문제를 3개 정도 풀어봤는데 현재까지 풀어본 케이스들은 거의 유사한 것 같다. 약간의 문제별 차이가 존재해서 코드를 짜는데는 여전히 너무 오랜 시간이 걸리지만... BFS 유형의 문제구나라는 확신이 온다면 다른 문제들에 비해서 접근 방식이 명확해질 것 같다. 결국 문제가 어떤 유형의 문제인지 파악하는 힘과 BFS 사용 연습을 많이해서 시간을 줄이는게 최선인 것 같다.