[백준] (Swift) 3184번 - 양 (실버1) (DFS)

친구와 DFS / BFS에 대한 고찰을 한 효과를 톡톡히 보는걸까? 이제 DFS와 BFS를 명확하게 구별할 줄 알고 문제가 쉽고 빠르게 풀린다..!

 

⚫️ 문제

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

3184번: 양

 

⚫️ 나의 풀이

앞서 풀었던 DFS 문제 유형과 계속 비슷하기 때문에 수월하게 풀이를 생각해냈다. 그리고 친구와 이야기 나눴던 부분을 잘 생각하면서 푸니까 금방 풀린다.. 올레 올레

영역마다 양과 늑대의 수를 따로 세어줘야하기 때문에, for 문을 돌려서 영역별로 탐색해주어야한다고 생각했다. 영역마다 탐색을 마치면 전부 # (울타리)로 값을 바꿔주면서 방문처리를 해주었다. 그리고 각 영역마다 양과 늑대의 수를 비교해서 총 answer을 구해주었다.!

문제를 풀기 전 아래처럼 그림을 그렸다.

이것을 그대로 코드로 옮기면 아래와 같이 정답코드를 작성할 수 있다!

 

⚫️ 정답코드 

import Foundation

let rc = readLine()!.split(separator: " ").map{ Int($0)! }
var field = [[String]]()
for _ in 0..<rc[0] {
    field.append(readLine()!.map{ String($0) })
}

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

var oCnt = 0
var vCnt = 0
var answer = [0, 0]

private func dfs(x: Int, y: Int) {
    switch field[x][y] {
    case "o":
        oCnt += 1
    case "v":
        vCnt += 1
    default:
        break
    }

    field[x][y] = "#"

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

        if nx < 0 || ny < 0 || nx >= rc[0] || ny >= rc[1] {
            continue
        }

        if field[nx][ny] != "#" {
            dfs(x: nx, y: ny)
        }
    }
}

for i in 0..<rc[0] {
    for j in 0..<rc[1] {
        if field[i][j] != "#" {
            oCnt = 0
            vCnt = 0
            dfs(x: i, y: j)

            if vCnt >= oCnt {
                answer[1] += vCnt
            } else {
                answer[0] += oCnt
            }
        }
    }
}

print("\(answer[0]) \(answer[1])")