[백준/Swift] 3184 : 양

 

 

• BOJ_3184.swift

• 3184 : / 문제 소개
• 풀이 과정
• 코드 구현

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

3184번: 양

3184 : 양 / 문제 소개

 

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

이 문제와 똑같은 문제이다.

---

주어진 input의 맵 안에 울타리가 있다.

양은 물론 늑대도 울타리 밖으로 달아날 수 없다.

울타리 안에서 양의 개수가 많을 경우 늑대를 다 잡아먹는다 그 반대의 경우 늑대가 양을 다 잡아먹는다.

풀이 과정

 

우선 양과 늑대의 좌표를 queue에 저장했다. 이후 한개씩 꺼내가며 bfs탐색을 통해 문제의 조건을 비교해 가면서 풀어갔다. queue에 이미 방문했던 좌표가 있으므로 visited (type : bool) 을 통해 방문했는가?를 체크를 해나갔다

코드 구현

 

/*
    이 문제는 울타리 # 안에서 양의수가 많으면 양을 추가 else 늑대 개수를 구하는 문제이다.
    bfs로 풀어나가면서 현재 큐에 저장된 좌표의 값이 양이냐 늑대냐를 카운트해가면서 풀어나갔다.
 */
import Foundation
let direction = [(-1,0),(1,0),(0,1),(0,-1)]
class mapInfo
{
    let height : Int
    let width  : Int
    var map    : [[String]]
    init(_ queue : inout [(Int,Int)])
    {
        let hw = readLine()!.split(separator:" ").map{Int(String($0))!}
        height = hw[0]
        width  = hw[1]
        map    = Array(repeating:[String](),count:height)
        for y in 0..<height
        {
            map[y] = readLine()!.map{String($0)}
            for x in 0..<width
            {
                if map[y][x] == "o" || map[y][x] == "v"
                {
                    queue.append((x,y))
                }
            }
        }
    }
}
func BFS(_ x : Int, _ y : Int,_ wolf : inout Int, _ sheep : inout Int, m : mapInfo, _ visited : inout [[Bool]])
{
    var queue     = [(x,y)]
    var index     = 0
    var tempWolf  = 0
    var tempSheep = 0
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        if m.map[curY][curX] == "v"
        {
            tempWolf += 1
        }
        else if m.map[curY][curX] == "o"
        {
            tempSheep += 1
        }
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx < 0 || nx > m.width - 1 || ny < 0 || ny > m.height - 1
            {
                continue
            }
            if m.map[ny][nx] != "#" && !visited[ny][nx]
            {
                visited[ny][nx] = true
                queue.append((nx,ny))
            }
        }
    }
    if tempSheep > tempWolf
    {
        sheep += tempSheep
    }
    else
    {
        wolf += tempWolf
    }
}
func BOJ_3184()
{
    var queue   = [(Int,Int)]()
    var index   = 0
    var wolf    = 0
    var sheep   = 0
    var m       = mapInfo(&queue)
    var visited = Array(repeating: Array(repeating: false, count: m.width), count: m.height)
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        index += 1
        if !visited[curY][curX]
        {
            visited[curY][curX] = true
            BFS(curX, curY, &wolf, &sheep, m: m, &visited)
        }
        
    }
    print("\(sheep) \(wolf)")
}
BOJ_3184()

 

visit my github