정의

구현이 빡센 문제들을 고-급스럽게 부르는 방식

import Foundation

let input1 = readLine()!.components(separatedBy: " ").map { Int($0)! }
let N = input1[0], M = input1[1]
var map: [[Int]] = {
  var map: [[Int]] = Array(repeating: [], count: N)
  for i in 0..<N {
    let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
    map[i] = line
  }
  return map
}()
let cameras: [[Int]] = {
  var result: [[Int]] = []
  for k in 0..<N {
    for i in 0..<M {
      if (1...5).contains(map[k][i]) {
        result.append([k, i])
      }
    }
  }
  return result
}()
var result = map.flatMap({ $0 }).filter { $0 == 0 }.count
var rx = [-1, 0, 1, 0] // 위 좌 상 우 순서로 이동
var ry = [0, -1, 0, 1]

func findSol(count: Int) { // 찾고 있는 지점 체크 포인트, CCTV가 보고 있으면 -1 표기
  if count == cameras.count {
    let newResult = map.flatMap({ $0 }).filter { $0 == 0 }.count
    result = min(result, newResult)
    return
  }

  let nx = cameras[count][0], ny = cameras[count][1]

  let tmpMap = map
  switch map[nx][ny] {
  case 1:
    for i in 0..<4 {
      map = createCCTVSight(cctvSightType: .init(rawValue: i)!, node: (nx, ny), curMap: map)
      findSol(count: count + 1)
      map = tmpMap
    }
  case 2:
    for i in 0..<2 {
      map = createCCTVSight(cctvSightType: .init(rawValue: i)!, node: (nx, ny), curMap: map)
      map = createCCTVSight(cctvSightType: .init(rawValue: (i+2)%4)!, node: (nx, ny), curMap: map)
      findSol(count: count + 1)
      map = tmpMap
    }
  case 3:
    for i in 0..<4 {
      map = createCCTVSight(cctvSightType: .init(rawValue: i)!, node: (nx, ny), curMap: map)
      map = createCCTVSight(cctvSightType: .init(rawValue: (i+1)%4)!, node: (nx, ny), curMap: map)
      findSol(count: count + 1)
      map = tmpMap
    }
  case 4:
    for i in 0..<4 {
      map = createCCTVSight(cctvSightType: .init(rawValue: i)!, node: (nx, ny), curMap: map)
      map = createCCTVSight(cctvSightType: .init(rawValue: (i+1)%4)!, node: (nx, ny), curMap: map)
      map = createCCTVSight(cctvSightType: .init(rawValue: (i+2)%4)!, node: (nx, ny), curMap: map)
      findSol(count: count + 1)
      map = tmpMap
    }
  case 5:
    map = createCCTVSight(cctvSightType: .init(rawValue: 0)!, node: (nx, ny), curMap: map)
    map = createCCTVSight(cctvSightType: .init(rawValue: 1)!, node: (nx, ny), curMap: map)
    map = createCCTVSight(cctvSightType: .init(rawValue: 2)!, node: (nx, ny), curMap: map)
    map = createCCTVSight(cctvSightType: .init(rawValue: 3)!, node: (nx, ny), curMap: map)

    findSol(count: count + 1)
    map = tmpMap
  default:
    return
  }
  return
}

enum cctvSightType: Int {
  case up
  case right
  case down
  case left
}

func createCCTVSight(cctvSightType: cctvSightType, node: (x: Int, y: Int), curMap: [[Int]]) -> [[Int]] {
  var newMap = curMap
  var step = 0

  switch cctvSightType {
  case .up: fallthrough
  case .down:
    while true {
      step += rx[cctvSightType.rawValue]
      guard node.x+step != N && node.x+step >= 0 else { break }
      guard newMap[node.x+step][node.y] != 6 else { break }
      guard !(1..<6).contains(newMap[node.x+step][node.y]) else { continue }
      newMap[node.x+step][node.y] = -1
    }

  case .right: fallthrough
  case .left:
    while true {
      step += ry[cctvSightType.rawValue]
      guard node.y+step != M && node.y+step >= 0 else { break }
      guard newMap[node.x][node.y+step] != 6 else { break }
      guard !(1..<6).contains(newMap[node.x][node.y+step]) else { continue }
      newMap[node.x][node.y+step] = -1
    }
  }

  return newMap
}

findSol(count: 0)
print(result)

stealmh commented 1 week ago

정의

구현이 빡센 문제들을 고-급스럽게 부르는 방식

??

MUKER-WON commented 1 week ago

시뮬레이션 (Simulation)

구현이 빡센 문제들을 고-급스럽게 부르는 방식

문제 풀이

백준 15683번: 감시

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

import Foundation

typealias Coor = (Int, Int) // 좌표
let I = readLine()!.split { $0 == " " }.map { Int($0)! }
let (N,M) = (I[0],I[1])
let D = [(1,0),(0,1),(-1,0),(0,-1)] // 하,우,상,좌
var ans = Int.max

var camera = [(Int,Int,Int)]() // y,x,카메라type
var office = (0..<N).map { i -> [Int] in
    let x = readLine()!.split { $0 == " " }.map { Int($0)! }
    (0..<M).forEach { j in
        if 1...5 ~= x[j] { camera += [(i,j,x[j])] }
    }
    return x
}

/// d 방향으로 감시영역을 구하는 함수
/// d: direction 즉 탐색하는 방향 (전역변수인 D의 index)
func observe(_ p: Coor, _ d: Int) -> [Coor] {
    var observeArr = [(Int, Int)]() // 감시된 영역
    var p = p
    while true {
        let (dy, dx) = (p.0 + D[d].0, p.1 + D[d].1)
        guard dy >= 0 && dy < N && dx >= 0 && dx < M else { break } // index 초과할 때 멈춤
        guard office[dy][dx] != 6 else { break } // 벽을 만났을 때 멈춤
        p = (dy,dx) // d방향으로 좌표 재설정
        if office[dy][dx] != 0 { continue } // 다른 감시카메라가 있을 때는 건너뛰기
        observeArr += [(dy, dx)]
    }
    return observeArr
}

/// count: camera 배열의 인덱스
func task(_ count: Int) {
    if count == camera.count {
        ans = min(ans, office.flatMap { $0 }.filter { $0 == 0 }.count) // 이부분이 너무 마음에 안듦.. 감시영역을 구하기 위해 항상 office배열을 완전탐색 하게 함
        return
    }
    let camera = camera[count]
    switch office[camera.0][camera.1] {
    case 1: // 1번째 감시 카메라 (상,하,좌,우)
        for i in 0..<4 {
            let arr = observe((camera.0, camera.1), i)
            arr.forEach { office[$0.0][$0.1] = 7 }
            task(count+1)
            arr.forEach { office[$0.0][$0.1] = 0 }
        }
    case 2: // 2번째 감시 카메라
        for i in 0...1 {
            var arr = observe((camera.0, camera.1), i)
            arr += observe((camera.0, camera.1), i+2)
            arr.forEach { office[$0.0][$0.1] = 7 }
            task(count+1)
            arr.forEach { office[$0.0][$0.1] = 0 }
        }
    case 3: // 3번째 감시 카메라
        for i in 0..<4 {
            var arr = [Coor]()
            for j in 0..<2 { arr += observe((camera.0, camera.1), (i+j)%4) }
            arr.forEach { office[$0.0][$0.1] = 7 }
            task(count+1)
            arr.forEach { office[$0.0][$0.1] = 0 }
        }
    case 4: // 4번째 감시 카메라
        for i in 0..<4 {
            var arr = [Coor]()
            for j in 0..<3 { arr += observe((camera.0, camera.1), (i+j)%4) }
            arr.forEach { office[$0.0][$0.1] = 7 }
            task(count+1)
            arr.forEach { office[$0.0][$0.1] = 0 }
        }
    case 5: // 5번째 감시 카메라
        var arr = [Coor]()
        for i in 0..<4 { arr += observe((camera.0, camera.1), i) }
        arr.forEach { office[$0.0][$0.1] = 7 }
        task(count+1)
        arr.forEach { office[$0.0][$0.1] = 0 }
    default : return
    }
}

task(0)
print(ans)

stealmh commented 1 week ago

시뮬레이션

말이좋아 시뮬레이션이지 사실은 노가다 구현방법을 뜻한다.

예제문제 15683 감시

코드

```swift import Foundation let input = readLine()!.split(separator: " ").map { Int($0)! } let n = input[0], m = input[1] var board = [[Int]]() typealias CCTV = (x: Int, y: Int, type: Int) enum Direction { case 위,아래,왼쪽,오른쪽 } var cctvList = [CCTV]() var minArea = Int.max for _ in 0..= cctvList.count { var count = 0 for i in board { count += i.filter({ $0 == 0 }).count } minArea = min(minArea, count) return } let cctv = cctvList[idx] for bd in allCaseCheck(cctv, board: board) { check(idx: idx + 1, board: bd) } } func makeSafeArea(x: Int, y: Int, direction: Direction, board: [[Int]]) -> [[Int]] { var x = x var y = y var board = board switch direction { case .위: while 0.. [[[Int]]] { var boards = [[[Int]]]() switch cctv.type { case 1: boards.append(makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: board)) boards.append(makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: board)) boards.append(makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: board)) boards.append(makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: board)) case 2: var leftAndRight = board var upAndDown = board leftAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: leftAndRight) leftAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: leftAndRight) boards.append(leftAndRight) upAndDown = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: upAndDown) upAndDown = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: upAndDown) boards.append(upAndDown) case 3: var upAndLeft = board var upAndRight = board var downAndLeft = board var downAndRight = board upAndLeft = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: upAndLeft) upAndLeft = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: upAndLeft) boards.append(upAndLeft) upAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: upAndRight) upAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: upAndRight) boards.append(upAndRight) downAndLeft = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: downAndLeft) downAndLeft = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: downAndLeft) boards.append(downAndLeft) downAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: downAndRight) downAndRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: downAndRight) boards.append(downAndRight) case 4: var upLeftRight = board var upLeftDown = board var leftDownRight = board var downRightUp = board upLeftRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: upLeftRight) upLeftRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: upLeftRight) upLeftRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: upLeftRight) boards.append(upLeftRight) upLeftDown = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: upLeftDown) upLeftDown = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: upLeftDown) upLeftDown = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: upLeftDown) boards.append(upLeftDown) leftDownRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: leftDownRight) leftDownRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: leftDownRight) leftDownRight = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: leftDownRight) boards.append(leftDownRight) downRightUp = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: downRightUp) downRightUp = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: downRightUp) downRightUp = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: downRightUp) boards.append(downRightUp) case 5: var all = board all = makeSafeArea(x: cctv.x, y: cctv.y, direction: .아래, board: all) all = makeSafeArea(x: cctv.x, y: cctv.y, direction: .오른쪽, board: all) all = makeSafeArea(x: cctv.x, y: cctv.y, direction: .위, board: all) all = makeSafeArea(x: cctv.x, y: cctv.y, direction: .왼쪽, board: all) boards.append(all) default: break } return boards } check(idx: 0, board: board) print(minArea) ```

qwerty3345 commented 1 week ago

개념

사실 그냥 빡구현.ㅋㅋㅋㅋㅋ
문제 많이 풀어보는 것 밖에 답이 없을듯

BOJ 15683번: 감시

코드

```swift let input = readLine()!.components(separatedBy: " ").compactMap { Int($0) } let (N, M) = (input[0], input[1]) // 보드, CCTV 위치 초기화 var board: [[Int]] = [] struct CCTV { let x: Int let y: Int let type: CCTVType var direction: Direction } enum Direction: Int, CaseIterable { case up case left case down case right } enum CCTVType: Int, CaseIterable { case oneSide = 1 case bothSide case angleSide case threeSide case allSide } let D = [(0, -1), (1, 0), (0, 1), (-1, 0)] // (상, 우, 하, 좌) var cctvs: [CCTV] = [] var minimumNumberOfBlindSpot: Int = .max for y in 0..= M || ny < 0 || ny >= N || monitoredBoard[ny][nx] == 6 { break } // 감시 가능한 영역에 표시 (0: 빈칸, 7: 감시된 구역) if monitoredBoard[ny][nx] == 0 { monitoredBoard[ny][nx] = 7 } } } for cctv in cctvs { switch cctv.type { case .oneSide: monitor(cctv, D[cctv.direction.rawValue]) case .bothSide: if cctv.direction == .up || cctv.direction == .down { monitor(cctv, D[0]) // 위 monitor(cctv, D[2]) // 아래 } else { monitor(cctv, D[1]) // 오른쪽 monitor(cctv, D[3]) // 왼쪽 } case .angleSide: monitor(cctv, D[cctv.direction.rawValue]) // 현재 방향 monitor(cctv, D[(cctv.direction.rawValue + 1) % 4]) // 90도 회전한 방향 case .threeSide: monitor(cctv, D[cctv.direction.rawValue]) // 현재 방향 monitor(cctv, D[(cctv.direction.rawValue + 1) % 4]) // 90도 monitor(cctv, D[(cctv.direction.rawValue + 3) % 4]) // -90도 case .allSide: for i in 0..<4 { monitor(cctv, D[i]) // 4방향 모두 감시 } } } let blindSpots = monitoredBoard .flatMap { $0 } .filter { $0 == 0 } .count minimumNumberOfBlindSpot = min(minimumNumberOfBlindSpot, blindSpots) } // 초기 탐색 시작 setCCTVDirection(0) print(minimumNumberOfBlindSpot) ```

TeddysRoom / Algo-rhythm

Simulation #5

정의

정의