[백준] (Swift) 14502번 - 연구소 (BFS 문제풀이)

🟠 문제 링크

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

14502번: 연구소

 

🟠 문제 풀이 아이디어

0과 1과 2를 구별해야한다는 점이 어려웠다. 역시 골드는 나에게 무리인것인가 ㅠㅠㅠ 실력언제늘어 늘고는 있니?

고민고민고민 하다가 도저히 감이 잡히지 않아서 어떻게 풀었나 참고를 해보았는데 풀이 방법은 다음과같았다.

• BFS는 어떻게 구현할까
  • 바이러스를 퍼뜨리는것이 목표기떄문에 바이러스를 queue에 넣어주고, 사방면에 위치한 값이 0 이라면, 2로 입력해주면서 BFS 를 돌렸다. 즉, BFS를 돌리면서 바이러스를 전파해주었다.
• 벽은 딱 세개 세울 수 있는데,  어떻게 세울까 
  • 파이썬으로 푼 풀이들은 대부분 조합..?? 뭐 쨋든 그 collection에서 제공하는 것으로 벽을 세울 수 있는 모든 경우의 수를 구한뒤, 해당 위치에 벽을 세개 새웠을때의 최대값을 구했다.
  • 하지만 swift는 이런기능이없어서 3중for문을 이용해서 0인 위치들을 전부 탐색하고, 이중에 세개의 위치를 골라서 1을 넣어준뒤차근차근 bfs를 돌려주었다 ^___^
• 핵심 포인트는, 0인 위치를 Empty 라는 변수에 모두 넣어준 뒤, 위치 3개의 조합을 모두 고려하여 전부 탐색해준다는 점이 포인트였다.

 

🟠 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/14502_%EC%97%B0%EA%B5%AC%EC%86%8C/main.swift

GitHub - deslog/Algorithm

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0] // 세로
let m = nm[1] // 가로
var lab = [[Int]]()
var empty = [(Int, Int)]()
var virus = [(Int, Int)]()
var max = 0
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

for _ in 0..<n {
    lab.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

for y in 0..<n {
    for x in 0..<m {
        if lab[y][x] == 0 {
            empty.append((y, x))
        } else if lab[y][x] == 2 {
            virus.append((y, x))
        }
    }
}

// bfs
// 바이러스를 전파시키면서 bfs돌려줌
func bfs(copyLab: Array<Array<Int>>) {
    var bfsLab = copyLab // lab을 바꿔버리면 안되기 때문에 마지막에 bfs돌릴 때 copy 해서 돌릴 거임
    var queue = [(Int, Int)]()
    var visited = Array(repeating: Array(repeating: false, count: m), count: n)
    var cnt = 0
    
    for i in 0..<virus.count {
        queue.append(virus[i])
    }

    while !queue.isEmpty {
        let yx = queue.removeFirst()
        let y = yx.0
        let x = yx.1
        
        for i in 0..<4 {
            let ny = y + dy[i]
            let nx = x + dx[i]
            
            // 범위 확인하고, 0 이면 2로 바꾸면서 바이러스 전파시킴, 그리고 방문처리
            if nx >= 0, ny >= 0, nx < m, ny < n {
                if bfsLab[ny][nx] == 0, visited[ny][nx] == false {
                    queue.append((ny, nx))
                    visited[ny][nx] = true
                    bfsLab[ny][nx] = 2
                }
            }
        }
    }
    
    // 0 세어주기
    for i in 0..<n {
        cnt += bfsLab[i].filter { ($0) == 0 }.count
    }
    
    // max 값 갱신해주기
    if max < cnt {
        max = cnt
    }
}

// 전체 돌면서 1 넣어주기
for i in 0..<empty.count {
    for j in 0..<i {
        for k in 0..<j {
            let y1 = empty[i].0
            let x1 = empty[i].1
            let y2 = empty[j].0
            let x2 = empty[j].1
            let y3 = empty[k].0
            let x3 = empty[k].1
            
            lab[y1][x1] = 1
            lab[y2][x2] = 1
            lab[y3][x3] = 1
            
            let newLab = lab
            bfs(copyLab: newLab)
            
            lab[y1][x1] = 0
            lab[y2][x2] = 0
            lab[y3][x3] = 0
        }
    }
}

print(max)

 

 

 

📖 Reference

아래 풀이를 참고했슴니다앙

https://cotak.tistory.com/14

[백준] 14502 - 연구소 [Python(파이썬)]