[백준/Swift] 17141 : 연구소2

...
if !visited[new탐색할y좌표][new탐색할x좌표]
{
visited[new탐색할y좌표][new탐색할x좌표] = visited[현재 탐색중인 y좌표][현재 탐색중이x좌표] + 1
...
}

 

• BOJ_17141.swift

• 17141 : 연구소2/ 문제 소개
• 풀이 과정
• 코드 구현

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

17141번: 연구소 2

17141 : 연구소2 / 문제 소개

 

연구소(n by n )에 벽 1, 바이러스 놓을 수 있는 칸 2, 바이러스 퍼질 수 있는 칸 0이 있다.

M은 바이러스의 개수이다.

연구소 안 특정 바이러스 놓을 수 있는 칸(2)에 바이러스를 놓을 때 가장 최소한의 시간에

전부 바이러스를 퍼지게 하는 최소 시간을 출력하는 문제이다.

 

이 문제를 풀기 위해선

바이러스가 퍼질 때 bfs를 사용해야 하고,

그 이전에 바이러스를 놓을 수 있는 칸들 중에 중복되지 않는 칸들을 선택(조합 : combination)해서 바이러스가 퍼질 수 있는 시간을 전부 구하고 그 중 벽을 제외한 모든 칸에 퍼지는 바이러스가 최소 시간인 것을 찾으면 답이다.

풀이 과정

 

우선 맵을 받아올 때 바이러스를 놓을 수 있는 칸들의 좌표을 List배열 에 저장했다.

typealias point = (x:Int,y:Int,time:Int)
map       = Array(repeating: [Int](), count: n)
var list      = [point]()

for y in 0..<n
        {
            map[y] = readLine()!.split(separator:" ").map{Int(String($0))!}
            for x in 0..<n
            {
                if map[y][x] == 2
                {
                    list.append((x,y,0))
                }
            }
        }

 

이 list의 index를 문제에서 주어진 놓을 수 있는 바이러스의 개수 M개를 선택해서 그 좌표들에 대해 bfs탐색을 하면된다.

 

여기서 중요한 것이 list.count == 5이고 M == 3 이라면

선택할 수 있는 원소들은 index로 표현할 수 있다.

0,1,2,3,4 중 3개..

 

이게 이 문제의 뽀인트인것 같다.(아닌가?)

0,1,2 | 0,1,3 | 0,1,4

1,2,3 | 1,2,4 | 1,2,5

1,3,4 | 1,3,5

2,3,4

이렇게 구하려면 재귀를 사용해야 한다.

let list = [0,1,2,3,4]

var selected = Array(repeating:false,count:list.count)

var dfs(_ index: Int, _ curCount: Int, _ needCount : Int)
{
	if curCount == needCount
    {
    	var result = ""
    	for i in 0..<selected.count
        {
        	if selected[i]
            {
            	//여기서 i는 선택된 index이다.
                result += "\(i) "
            }
        }
        print(result)
        return
    }
    
    for i in index..<list.count
    {
    	if selected[i] { continue }
        selected[i] = true
        dfs(i+1,curCount+1,needCount)
        selected[i] = false
    }
}

dfs(0,0,3)

재귀는 이런 형식으로 구현할 수 있다.

여기서 selected가 중요하다. 이것을 통해 특정 index들이 중복해서 선택되지 않게 해준다.

 

이렇게 index 조합을 구성하면 바이러스를 퍼트리고 최소시간을 체크 후 이전에 구한 시간과 비교하면 된다.

근데 아무리 선택해도 바이러스가 퍼지지 않는 부분이 있어서 이 부분도 체크를 해야한다.

---

참고,,

추가로 bfs탐색시에 시간 체크를 어떻게 하는지 간략하게 설명하겠다,,

queue의 타입은 point이다.(위에..정의했어요)

point의 x,y는 탐색할 좌표이고, time은 bfs탐색할 때 동시에 탐색을 이어나가기 위한 체크인 겸?? 최소시간을 체크한다.

왼쪽은 초기 큐 오른쪽은 bfs탐색을 1회 했을 때의 큐이다.

이걸 visited[[Int]] 2차원 배열에 저장해 나가도 되지만,

...
if !visited[new탐색할y좌표][new탐색할x좌표]
{
visited[new탐색할y좌표][new탐색할x좌표] = visited[현재 탐색중인 y좌표][현재 탐색중이x좌표] + 1
...
}

queue의 x,y 좌표뒤에 저장해 나가도 된다.

그 코드는 아래에 있다!!

코드 구현

 

import Foundation
//탐색할 x,y좌표 그때의 진행 상황
typealias point = (x:Int,y:Int,time:Int)
//탐색할 방향
let direction   = [(-1,0),(1,0),(0,1),(0,-1)]
//최소시간 저장
var result      = 2501

/**
 TODO : 맵의 정보를 저장하는 클래스
 
 - Param n : 맵 크기
 - Param totalCnt : 선택해야 할 바이러스 M개 개수
 - Param map : 맵 정보
 - Param list : 맵에서 바이러스를 놓을 수 있는 좌표들 저장
 */
class mapInfo
{
    let n        : Int
    let totalCnt : Int
    var map      : [[Int]]
    var list     : [point]
    init()
    {
        let input = readLine()!.split(separator:" ").map{Int(String($0))!}
        n         = input[0]
        totalCnt  = input[1]
        map       = Array(repeating: [Int](), count: n)
        list      = [point]()
        for y in 0..<n
        {
            map[y] = readLine()!.split(separator:" ").map{Int(String($0))!}
            for x in 0..<n
            {
                if map[y][x] == 2
                {
                    list.append((x,y,0))
                }
            }
        }
    }
}

/**
 dfs를 통해 특정 index를 선택했다면 queue에 삽입될 것이고 해당 큐를 통해 바이러스가 퍼짐
 
 - parameter m: 맵 정보.
 - parameter visited: (중복 방문 안되기 위해) 방문 체크.
 - parameter queue: 선택된 바이러스 좌표들.
 
 # Notes: #
 1. 만약 바이러스가 선택됬음에도 바이러스가 퍼지지 않는 칸이 있을 수 있다.
    그래서 마지막에 완전 탐색으로 파악해준다.
 */
func bfs(_ m : mapInfo, _ visited : inout [[Bool]], _ queue : inout [point])
{
    var index = 0
    var time  = 0
    while queue.count != index
    {
        let (curX,curY,prevTime) = queue[index]
        index += 1
        if time == prevTime
        {
            time += 1
        }
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx<0||nx>m.n-1||ny<0||ny>m.n-1||visited[ny][nx] { continue }
            if m.map[ny][nx] != 1
            {
                visited[ny][nx] = true
                queue.append((nx,ny,prevTime+1))
            }
        }
    }
    if time > result
    {
        return
    }
    for y in 0..<m.n
    {
        for x in 0..<m.n
        {
            if !visited[y][x] && m.map[y][x] != 1
            {
                return
            }
        }
    }
    result = time
}

/**
 바이러스들이 있는 list에서 M개의 바이러스를 선택하기 위한 함수
 
 - parameter index: 선택될 숫자의 시작.
 - parameter curCnt: dfs함수 실행될 때 현재 몇개의 index들을 선택했는지?
 - parameter selected: 선택된 숫자들을 체크하는 배열.
 - parameter map: 맵 정보. 여기에 바이러스가 놓일 좌표들이 있는 list가 있음
 
 # Notes: #
 1. if curCnt == m.totalCnt
    만약 바이러스 놓을 수 있는 특정 개수를 선택했다면
    queue에 그 바이러스들 추가시키고 bfs탐색하기!!
 */
func dfs(_ index : Int,_ curCnt : Int,_ selected : inout [Bool],_ m : mapInfo )
{
    if curCnt == m.totalCnt
    {
        var queue   = [point]()
        var visited = Array(repeating:Array(repeating:false,count:m.n),count:m.n)
        for i in 0..<m.list.count
        {
            if selected[i]
            {
                let (x,y,time) = m.list[i]
                visited[y][x] = true
                queue.append((x,y,time))
            }
        }
        bfs(m, &visited, &queue)
        return
    }
    for i in index..<m.list.count
    {
        if selected[i] { continue }
        selected[i] = true
        dfs(i+1,curCnt+1, &selected, m)
        selected[i] = false
    }
}

// m = 맵 정보
// dfs호출 시 시작은 index 0 부터!! 이때 현재 선택된 개수도 0부터
func BOJ_17141()
{
    let m        = mapInfo()
    var selected = Array(repeating:false,count:m.list.count)
    dfs(0,0, &selected, m)
    print(result == 2501 ? -1 : result - 1)
}
BOJ_17141()

 

visit my github