[Swift 알고리즘] 백준 1799 비숍

 

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

1799번: 비숍

 

 

첫번째 dfs탐색

 

시간초과 모든 정점 다 들리는 것은 비 효율적임을 깨달았습니다.

import Foundation

func sol() {
  let n = Int(readLine()!)!
  let arr = (0..<n).map{_ in readLine()!.split(separator: " ").map{Int($0)!}}
  var visited: [[Int]] = arr
  var res: Int = 0
  let steps = [[1, 1], [1, -1], [-1, -1], [-1, 1]]
  func dfs(_ row: Int, _ col: Int, _ prev: Int) {
    res = max(res, prev)
    let (dfsRow, dfsCol) = col + 1 >= n ? (row + 1, 0) : (row, col + 1)
    if dfsRow >= n {
      return
    }
    
//    print(row, col, "\n", visited.map{$0.map{String($0)}.joined(separator: " ")}.joined(separator: "\n"))
    if arr[row][col] == 1 && visited[row][col] != -1{
      let curVisited = visited
      for step in steps {
        var nr = row + step[0]
        var nc = col + step[1]
        while 0 <= nr && nr < n && 0 <= nc && nc < n {
          visited[nr][nc] = -1
          nr += step[0]
          nc += step[1]
        }
      }
      visited[row][col] = -1
      dfs(dfsRow, dfsCol, prev + 1)
      visited = curVisited
    }
    dfs(dfsRow, dfsCol, prev)
  }
  dfs(0, 0, 0)
  print(res)
}

sol()

 

 

 

 

 

 

두번째 풀이

어차피 비숍은 대각선으로만 이동하기 때문에, 현재 row, col을 추가하는 것은 대각선을 추가하는 것과 같습니다. 사진처럼 가운데 점을 추가하게 되면 대각선 두개에 있는 선분에 있는 점들은 고려할 필요가 없어집니다. 

 

여기까지는 생각 했지만 어떻게 대각선을 visited할까에 대해서 고민했습니다. 결국 해답을 찾지 못해 블로그를 참고해서 우하향 그래프의 대각선 구하는 공식과, 좌하향 그래프의 대각선 그래프 공식을 참고했습니다. 

rv[col - row + n - 1]

lv[row + col]

 

import Foundation
func sol() {
  let n = Int(readLine()!)!
  let arr = (0..<n).map{_ in readLine()!.split(separator: " ").map{Int($0)!}}
  var rv = Array(repeating: false, count: 2 * n)
  var lv = Array(repeating: false, count: 2 * n)
  var res: Int = 0
  func dfs(_ row: Int, _ col: Int, _ prev: Int) {
    if row >= n {
      res = max(res, prev)
      return
    }
    var dfsRow = row
    var dfsCol = col + 2
    if dfsCol >= n {
      dfsRow += 1
      dfsCol = dfsCol % 2 == 0 ? 1 : 0
    }
    
    if arr[row][col] == 1 && !rv[col - row + n - 1] && !lv[row + col]{
      rv[col - row + n - 1] = true
      lv[row + col] = true
      dfs(dfsRow, dfsCol, prev + 1)
      rv[col - row + n - 1] = false
      lv[row + col] = false
    }
    dfs(dfsRow, dfsCol, prev)
  }
  dfs(0, 0, 0)
  let t1 = res
  res = 0
  dfs(0, 1, 0)
  let t2 = res
  print(t1 + t2)
}

sol()

 

 

추가

처음부터 row, col로 안하고, 입력으로 받은 대각선 집합을 통해 dfs탐색하는 것이 빠를 것으로 생각합니다.