[Swift] 백준, 연구소

문제 링크

백준 알고리즘 - 연구소

풀이

이번엔.. 맞췄습니다. 그런데 사실 상 방법 자체를 모르겠어서 다른 블로그를 좀 참고했습니다.

너무 어렵네요..

풀이 방식은 간단합니다.

1. 완전 탐색으로 벽을 만든다.
2. 바이러스가 있는 좌표를 구해서 바이러스를 기점으로 bfs를 돌면서 바이러스를 퍼트린다.
3. 안전 구역을 구한다.

네.. 이렇게 구하면 돼요! 이 문제가 어렵다고 느껴졌던 이유는.. 벽을 3개 만들라는데, 효율적으로 만들어야하나? 라는 생각이 들어서였던 것 같아요

근데 보니까 메모리 제한은 있는데, 시간 제한은 없더라구요 ㅎㅎ 😄

문제 확인할 때, 이런 부분도 다 체크를 해봐야겠어요 앞으로는! “시간 제한이 없다면 완전탐색도 고려해보자”가 이 문제의 교훈이었습니다.

코드

함수 네이밍은 음.. 신경쓸까하다가.. 어차피 알고리즘 문제니까 그냥 대충 했습니다 ㅜㅜ

보기 불편하실 수 있긴한데, 감안해서 봐주세요 ㅎㅎ 죄송합니다. 🙏🏻

//
//  main.swift
//  연구소
//
//  Created by 남기범 on 2020/12/26.
//  Copyright © 2020 남기범. All rights reserved.
//

import Foundation

let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let x = line[0]
let y = line[1]

var arr = Array(repeating: Array(repeating: 0, count: y), count: x)

for i in 0..<x {
    let arrLine = readLine()!.components(separatedBy: " ").map { Int($0)! }
    for j in 0..<y {
        arr[i][j] = arrLine[j]
    }
}

var safeArea = [(Int, Int)]()

for i in 0..<x {
    for j in 0..<y where arr[i][j] == 0 {
        safeArea.append((i,j))
    }
}

makeWall(arr)

func makeWall(_ array: [[Int]]) {
    var result = 0
    
    for i in 0..<safeArea.count {
        for j in i+1..<safeArea.count {
            for k in j+1..<safeArea.count {
                let point1 = safeArea[i]
                let point2 = safeArea[j]
                let point3 = safeArea[k]
                
                var array = array
                
                array[point1.0][point1.1] = 1
                array[point2.0][point2.1] = 1
                array[point3.0][point3.1] = 1
                
                result = max(result, makeVirus(array))
            }
        }
    }
    
    print(result)
}

func makeVirus(_ array: [[Int]]) -> Int {
    var array = array
    let pointY = [-1, 0, 1 , 0]
    let pointX = [0, -1, 0, 1]
    var virusArr = virusArea(array)
    
    while !virusArr.isEmpty {
        let startPoint = virusArr.removeFirst()
        
        for i in 0..<4 {
            let nx = startPoint.0 + pointX[i]
            let ny = startPoint.1 + pointY[i]
            
            if pointChecker(nx, ny) && array[nx][ny] == 0 {
                array[nx][ny] = 2
                virusArr.append((nx, ny))
            }
        }
    }
    
    let result = resultSafeArea(array)
    return result.count
}

func pointChecker(_ n: Int, _ m: Int) -> Bool {
    return n >= 0 && m >= 0 && n<x && m<y
}

func virusArea(_ array: [[Int]]) -> [(Int, Int)] {
    var result = [(Int, Int)]()
    
    for i in 0..<array.count {
        for j in 0..<array[i].count where array[i][j] == 2 {
            result.append((i, j))
        }
    }
    
    return result
}

func resultSafeArea(_ array: [[Int]]) -> [(Int, Int)] {
    var result = [(Int, Int)]()
    
    for i in 0..<array.count {
        for j in 0..<array[i].count where array[i][j] == 0 {
            result.append((i, j))
        }
    }
    
    return result
}