[백준/Swift] 18405 : 경쟁적 전염

 

 

• BOJ_18405()

• 18405 : 경쟁적 전염/ 문제 소개
• 풀이 과정
• 코드 구현

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

18405번: 경쟁적 전염

 

18405 : 경쟁적 전염/ 문제 소개

 

이 문제는 시험관 안에 초기 바이러스들이 존재한다.

이때 바이러스는 1~K 번까지 반드시 존재한다. 이때 주의할 점이 특정 바이러스 종류가 여러 개 존재할 수 있다. 

왼쪽 그림은 k = 3일때 초기 바이러스 위치이다. 

1초마다 바이러스들은 상 하 좌 우로 전염될 수 있는데 번호가 낮은 종류의 바이러스부터 먼저 증식된다.

특정 칸에 바이러스 존재할 경우 다른 바이러스로 증식 x.

 

S초가 지난 후에 (x,y)에 존재하는 바이러스의 종류가 0이 아니라면 해당 바이러스 존재를 출력한다.

존재하지 않을 경우 특정 바이러스 종류를 출력하면 된다.

 

주의할 점은 왼쪽 시험관 그림을 봤을 때 1번 종류의 바이러스 위치는 (  1 , 1 ) 에 위치한다고 입력값(s 초의 x , y )에서 주어진다는 것이다.

 

풀이 과정

 

주의할 점

• 특정 바이러스 종류가 여러개 존재
• 번호가 낮은 종류의 바이러스부터 증식
• 가장 왼쪽 위 시험관의 좌표는 1,1로 주어진다.

이 주의할 점 을 다 고려하여 문제를 풀면 될 것 같습니다.

 

bfs를 통해 풀었습니다.

특정 바이러스의 위치를 담는 queue를 종류마다 저장할 수 있는 qList를 구현했습니다.

 

 

코드 구현

 

import Foundation

// 탐색할 x좌표, y좌표, 탐색 당시의 시간 저장
typealias Element = (x: Int, y: Int, prevTime : Int)

// 탐색할 방향 [(왼쪽)(오른쪽)(위)(아래)]
let direction     = [(-1,0),(1,0),(0,1),(0,-1)]

/**
 * 특정 virus가 위치한 좌표를 저장할 Q입니다.
 * index를 통해 queue를 탐색해 나갑니다.
 */
class Q
{
    var queue : [Element]
    var index : Int
    init()
    {
        queue = [Element]()
        index = 0
    }
}

/**
 * 초기 바이러스 탐색하는 함수
 * **주의**
 * 이때 특정 바이러스는 1개 이상 존재할 수 있습니다.
 * 이때 구성된 q는 특정한 한개의 바이러스에 대한 좌표 들을 저장하는 큐이므로
 * 추후 qList( 큐 들을 저장하는 배열) 에 저장되어 관리됩니다.
 */
func initialVirus(_ n : Int, _ virus : Int,_ q : inout Q, _ map: [[Int]])
{
    for y in 0..<n
    {
        for x in 0..<n
        {
            if map[y][x] == virus
            {
                q.queue.append((x,y,0))
            }
        }
    }
}

/**
 * qList의 특정한 바이러스
 * 예를들어 바이러스 종류 == 2 이면 qList[1]의 Q클래스는 바이러스 번호 2인 바이러스 좌표들을 갖고 있는데
 *  이 특정 바이러스(예를들어 바이러스 번호 2라 가정했을때)를 담는 queue = qList[1] 이 대입됩니다.
 *
 * 따라서 이 함수는 특정 바이러스 번호의 좌표를 가지고 탐색 시간이 특정한 초 이전에만 탐색되도록 하는 bfs함수입니다.
 */
func bfs(_ n : Int, _ time : inout Int, _ virus : Int, _ s : Int, _ sPoint : (Int,Int), _ map : inout [[Int]], queue : inout Q)
{
    while queue.queue.count != queue.index
    {
        let (curX,curY,prevTime) = queue.queue[queue.index]
        if prevTime == time
        {
            return
        }
        queue.index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1 { continue }
            if map[ny][nx] == 0
            {
                map[ny][nx] = map[curY][curX]
                
                queue.queue.append((nx,ny,prevTime + 1))
            }
        }
    }
}

/**
 * @param time : 현재 시간
 *      이 시간을 기준으로 bfs()함수가 작업됩니다.
 */
func spreadVirus(_ n : Int, _ kind : Int,_ s : Int,_ sPoint : (Int,Int), _ map : inout [[Int]], _ qList : inout [Q])
{
    var time = 0
    while true
    {
        if time == s + 1
        {
            if map[sPoint.0][sPoint.1] == 0
            {
                print(0)
                return
            }else
            {
                print(map[sPoint.0][sPoint.1])
                return
            }
        }
        //바이러스 종류는 1~ K개 까지 반드시 존재하기 때문에 포문을 통해 bfs탐색을 하고 시간을 증가시킵니다.
        for virus in 0..<kind
        {
            bfs(n, &time, virus + 1, s, sPoint, &map, queue: &qList[virus])
        }
        time += 1
    }
}
/**
 * @param kind    : 바이러스 종류 개수
 * @param map    : 시험관
 * @param qList   : 특정 바이러스의 좌표를 담은 Q클래스의 배열
 * @param s         : 특정 시간
 * @param sPoint : 특정 시간에서 원하는 좌표
 */
func BOJ_18405()
{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let n     = input[0]
    let kind  = input[1]
    var map   = Array(repeating: [Int](), count: n)
    var qList = Array(repeating: Q(), count: kind)
    for y in 0..<n
    {
        map[y] = readLine()!.split(separator: " ").map{Int(String($0))!}
    }
    let sxy    = readLine()!.split(separator: " ").map{Int(String($0))!}
    let s      = sxy[0]
    let sPoint = (sxy[1] - 1,sxy[2] - 1)
    for virus in 0..<kind
    {
        var queue = Q()
        initialVirus(n, virus + 1, &queue, map)
        qList[virus] = queue
    }
    spreadVirus(n, kind,s,sPoint, &map, &qList)
}
BOJ_18405()