[완전 탐색] 백준 실버2 3085번: 사탕 게임(Swift)

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

3085번: 사탕 게임

풀이과정

이번 문제는,

N x N 보드에 무작위로 4가지 색의 사탕이 올라가있다.

보드에 올라가있는 사탕 중 인접한 색이 다른 사탕 2개의 자리를 바꿔 가로 혹은 세로로 연속한 같은 색의 사탕의 최댓값을 출력하는 문제이다.

문제를 처음 읽고 풀이를 생각했을 때 색이 서로 다른 인접한 사탕 2개를 탐색하여 위치를 변경하고 동일한 색의 연속한 사탕의 수를 계산하였다.

// 첫 제출

let N = Int(readLine()!)!
var input: [[String]] = []
var map: [[String]] = []
var result = 0

for _ in 0..<N {
  let y = Array(readLine()!).map { String($0) }
  input.append(y)
}


for y in 0..<N {
  for x in 0..<N {
    if (0..<N).contains(x+1) && input[y][x] != input[y][x+1] {
      map = input
      let t = map[y][x]
      map[y][x] = map[y][x+1]
      map[y][x+1] = t
      result = max(result, hori())
      result = max(result, ver())
    }
    
    if (0..<N).contains(y+1) && input[y][x] != input[y+1][x] {
      map = input
      let t = map[y][x]
      map[y][x] = map[y+1][x]
      map[y+1][x] = t
      result = max(result, hori())
      result = max(result, ver())
    }
  }
}
print(result)


func hori() -> Int {
  var value = 0
  for y in 0..<N {
    var target = ""
    var count = 1
    for x in 0..<N {
      if map[y][x] == target {
        count += 1
      } else {
        target = map[y][x]
        value = max(value, count)
        count = 1
      }
    }
    value = max(value, count)
  }
  return value
}

func ver() -> Int {
  var value = 0
  for x in 0..<N {
    var target = ""
    var count = 1
    for y in 0..<N {
      if map[y][x] == target {
        count += 1
      } else {
        target = map[y][x]
        value = max(value, count)
        count = 1
      }
    }
    value = max(value, count)
  }
  return value
}

위 코드는 서로 다른 사탕을 탐색하는 부분도, 가로 세로 연속된 사탕의 수를 계산하는 메서드 ver()과 hori()도 모두 이중 for 문으로 구현되어 있다.

위 코드를 제출해도 성공할 수 있지만, 꽤나 시간 복잡도가 높다.

시간 복잡도를 줄일 수 있는 방법을 생각해 보았다.

방법은 사탕의 위치를 변경하는 로직에서 두 사탕이 서로 달라야지만 위치를 변경했다면, 이젠 색 상관없이 (0, 0)부터 (N, N)까지 모두 위치를 바꾼다.

대신 위치를 바꾸고 위치가 변경된 행과 열만 사탕의 수를 탐색한다.

// 두번째 제출

let N = Int(readLine()!)!
var input: [[String]] = []
var map: [[String]] = []
var result = 0

for _ in 0..<N {
  let y = Array(readLine()!).map { String($0) }
  input.append(y)
}


for y in 0..<N {
  for x in 0..<N {
    if (0..<N).contains(x+1) {
      map = input
      let t = map[y][x]
      map[y][x] = map[y][x+1]
      map[y][x+1] = t
      result = max(result, hori(y: y))
      result = max(result, ver(x: x))
      result = max(result, ver(x: x+1))
    }
    
    if (0..<N).contains(y+1) {
      map = input
      let t = map[y][x]
      map[y][x] = map[y+1][x]
      map[y+1][x] = t
      result = max(result, hori(y: y))
      result = max(result, hori(y: y+1))
      result = max(result, ver(x: x))
    }
  }
}
print(result)


func hori(y: Int) -> Int {
  var value = 0
  var target = ""
  var count = 1
  for x in 0..<N {
    if map[y][x] == target {
      count += 1
    } else {
      target = map[y][x]
      value = max(value, count)
      count = 1
    }
  }
  value = max(value, count)
  return value
}

func ver(x: Int) -> Int {
  var value = 0
  var target = ""
  var count = 1
  for y in 0..<N {
    if map[y][x] == target {
      count += 1
    } else {
      target = map[y][x]
      value = max(value, count)
      count = 1
    }
  }
  value = max(value, count)
  return value
}

그럼 위와 같이 코드를 작성할 수 있고, 첫 제출과 다른 점은 ver() 메서드와 hori() 메서드 각각 y와 x를 고정하여 하나의 for 문 만을 사용하여 로직을 작성하였다.

이처럼 코드를 수정할 경우 위치를 바꾸는 경우의 수는 늘 수 있지만, 시간 복잡도가 줄어 결과적으로 실행 시간을 단축시킬 수 있다.