[백준 3184] 양 (Swift)

문제 : 

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

3184번: 양

 

1. 문제 이해하기

• 크기 3 <= 행, 열 <= 250의 그래프에 필드(.), 울타리(#), 늑대(v), 양(o)이 주어집니다.
• 울타리(#)로 둘러싸인 곳마다 해당 울타리 안에서의 늑대와 양의 개수 중 양의 개수가 더 많으면 양의 개수만 세고, 늑대와 양의 개수가 같거나 늑대의 개수가 더 많으면 늑대의 개수만 셉니다.
• 최종적으로 남는 양의 개수, 늑대 개수를 출력합니다.

 

2. 문제 풀이 생각하기

1. 처음에는 데 큐에 모든 늑대의 좌표를 다 넣고 시작을 하려고 했는데, 울타리마다의 개수를 셀 수 없어서 방법을 바꿨습니다.
2. 중첩 for문으로 graph를 보면서 방문 체크가 안 되어있는 칸이면 해당 칸부터 bfs를 시작합니다.
3. 큐에 방문할 좌표를 넣고, '#', '.', 'w', 'o' 각각의 케이스를 나누어서 처리합니다.
4. '#'는 방문처리만 하고, '.'는 방문처리 및 큐에 넣기, 'w', 'o'는 방문처리 후, 각각의 개수를 하나 더하고 큐에 넣습니다.
5. 각 울타리마다 남은 양, 늑대의 수를 ans에 더하기
6. 2 ~ 5 반복

 

3. 차근차근 구현하기

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var g = Array(repeating: Array(repeating: ".", count: m), count: n)
var q = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
let d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
var ans = [0, 0]
for i in 0..<n {
    let line = Array(readLine()!)
    for j in 0..<m {
        g[i][j] = String(line[j])
    }
}

func boundary(i: Int, j: Int) -> Bool {
    return (0 <= i && i < n) && (0 <= j && j < m)
}

func bfs(i: Int, j: Int) {
    q.append([i, j])
    visited[i][j] = true
    var numOfSheep = g[i][j] == "o" ? 1 : 0 // 처음 방문한 칸이 'o'일 때
    var numOfWolf = g[i][j] == "v" ? 1 : 0 // 처음 방문한 칸이 'v'일 때
    while !q.isEmpty {
        let now = q.removeFirst()
        let (i, j) = (now[0], now[1])
        for k in d {
            let ni = i + k[0]
            let nj = j + k[1]
            if !boundary(i: ni, j: nj) || visited[ni][nj] {
               continue
            }
            if g[ni][nj] == "#" {
                visited[ni][nj] = true
                continue
            }
            if g[ni][nj] == "." {
                visited[ni][nj] = true
                q.append([ni, nj])
                continue
            }
            if g[ni][nj] == "v" {
                visited[ni][nj] = true
                numOfWolf += 1
                q.append([ni, nj])
                continue
            }
            if g[ni][nj] == "o" {
                visited[ni][nj] = true
                numOfSheep += 1
                q.append([ni, nj])
                continue
            }
        }
    }
    if numOfSheep > numOfWolf {
        ans[0] += numOfSheep
    }
    else {
        ans[1] += numOfWolf
    }
}

for i in 0..<n {
    for j in 0..<m {
        if !visited[i][j] {
            bfs(i: i, j: j)
        }
    }
}
print(ans[0], ans[1])

 

4. 피드백

• 문제를 더 많이 풀어봐야 할 것 같습니다.