[Swift] 백준 15683, 14503

1. 문제: https://www.acmicpc.net/problem/15683

✅ 풀이

import Foundation

let readline = readLine()!.split(separator:" ").map { Int($0)! }
let (n, m) = (readline[0], readline[1])
var board:[[Int]] = []
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]
// 우 하 좌 상 순서 offset 배열
var answer = Int.max
var cctvs:[(Int, Int)] = []

for i in 0..<n {
  board.append(readLine()!.split(separator:" ").map { Int($0)! })
  for j in 0..<m {
    if Array(1...5).contains(board[i][j]) {    // 1, 2, 3, 4, 5는 cctv이므로 cctv 좌표를 배열에 저장
      cctvs.append((i, j))
    }
  }
}

func isValidCoord(_ x: Int, _ y: Int) -> Bool {    // 유효한 좌표 내에 있는지 판단하는 함수
  return 0 <= x && x < n && 0 <= y && y < m
}

func setMonitor(_ x:Int, _ y: Int, _ dir: Int) {
  var x = x
  var y = y
  let dir = dir%4    // dir가 인덱스 범위를 넘어설 때 벗어나지 않되 같은 offset을 가리키도록 하는 식

  while true {
    x += dx[dir]
    y += dy[dir]

    if !isValidCoord(x, y) || board[x][y] == 6 { break }    // 좌표를 벗어나거나, 벽을 마주쳤을 경우 해당 경우에서 cctv의 감시가 끝남
    if board2[x][y] == 0 {
      board2[x][y] = -1  // cctv 감시범위로 두기
    }
  }
}

var board2 = board

for i in 0..<Int(pow(4.0, Double(cctvs.count))) {
  var brute = i
  board2 = board   // 좌표마다 매번 조합이 달라져야하므로 원본 복사 후 시작
  for j in 0..<cctvs.count {
    let dir = brute % 4     // 4진법을 통해 각 cctv별 방향 정하기
    brute /= 4
    let (x, y) = cctvs[j]
    let number = board[x][y]

    switch number {
      case 1:
      setMonitor(x, y, dir)
      case 2:
      setMonitor(x, y, dir)
      setMonitor(x, y, dir+2)
      case 3:
      setMonitor(x, y, dir)
      setMonitor(x, y, dir+1)
      case 4:
      setMonitor(x, y, dir)
      setMonitor(x, y, dir+1)
      setMonitor(x, y, dir+2)
      case 5:
      setMonitor(x, y, dir)
      setMonitor(x, y, dir+1)
      setMonitor(x, y, dir+2)
      setMonitor(x, y, dir+3)
      default:
      break
    }
  }

  var count_zero = 0

  for k in 0..<n {
    for l in 0..<m {
      if board2[k][l] == 0 {
        count_zero += 1
      }
    }
  }

  answer = min(answer, count_zero)
}

print(answer)

 

- 해당 문제의 핵심은 모든 cctv의 모든 방향의 조합을 어떻게 계산하여 완전탐색을 수행할 것인가이다.

 

- 위와같이 예를들어 cctv의 갯수가 3개라면, 회전이 90도 이므로 한 cctv마다 회전할 수 있는 회전의 가짓수는 4개이다.

- 즉 4**3 = 64번이 각 cctv를 회전하면서 사각지대를 찾을 수 있는 모든 조합의 갯수이다.

- 문제는 여기서 어떻게 각 cctv의 방향을 정하냐 인데, 방향이 총 4가지이므로 4진수를 구함으로써 방향을 정할 수 있다.

- 10진수를 구할 때 10의 나머지를 구한 다음 10으로 나누듯이, 4진수도 마찬가지로 4의 나머지를 구한 다음 4로 나누는 방식으로 4진수를 구할 수 있다.

2. 문제: https://www.acmicpc.net/problem/14503

 

✅ 풀이

import Foundation

let readline = readLine()!.split(separator:" ").map { Int($0)! }
let (n, m) = (readline[0], readline[1])
var board:[[Int]] = []
let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]
// 문제조건 -> 인덱스 0: 북, 인덱스 1: 동, 인덱스 2: 남, 인덱스 3: 서
var answer = 0
let readline2 = readLine()!.split(separator:" ").map { Int($0)! }
var (r, c, d) = (readline2[0], readline2[1], readline2[2])
// (r, c): 로봇 청소기의 처음 위치, d: 방향

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

func isValidCoord(_ x: Int, _ y: Int) -> Bool {   // 유효한 좌표인지 판단하는 함수
  return 0 <= x && x < n && 0 <= y && y < m
}

func rotate(_ d: Int) -> Int {   // 반시계 방향으로 90도 회전
  if d == 0 {
    return 3
  } else {
    return d - 1
  }
}

var nr = 0, nc = 0

while true {
  // 1. 현재 칸이 청소되지 않았다면, 청소한다
  if board[r][c] == 0 {
    board[r][c] = 2
    answer += 1
  }
  var flag = false   // 주변에 청소 안한 구역이 있는지 판단하는 flag 변수

  for i in 0..<4 {
    nr = r + dx[i]
    nc = c + dy[i]

    guard isValidCoord(nr, nc) else { continue }
    if board[nr][nc] == 0 {   // 청소되지 않은 빈칸이 있음
      flag = true
    }
  }

  // 3. 청소되지 않은 빈칸이 있는 경우,
  if flag {
    d = rotate(d)   // 반시계 방향으로 90도 회전한다.

    nr = r + dx[d]
    nc = c + dy[d]

    guard isValidCoord(nr, nc) else { continue }
    if board[nr][nc] == 0 {   // 청소되지 않은 빈칸인 경우 전진한다.
      r = nr
      c = nc
    }
  } else {    // 2. 청소되지 않은 빈칸이 없는 경우,
    nr = r - dx[d]    // 후진한 좌표
    nc = c - dy[d]

    guard isValidCoord(nr, nc) else { continue }
    if board[nr][nc] == 1 {   // 벽이라서 후진할 수 없으므로 작동 멈춤
      break
    } else {   // 벽이 아니라서 후진할 수 있으므로 후진함
      r = nr
      c = nc
    }
  }
}

print(answer)

 

오늘 알게 된 점

- 시뮬레이션 문제를 보면, 함수화할 수 있는 지점을 찾아 함수화하는 습관을 들이자

- 좌표 관련된 문제는 먼저 유효한 좌표인지 판단하는 함수, offset (dx, dy) 배열을 습관적으로 만들자.