문제 정보


image

풀이

브루스 포스 알고리즘

  • Brute(무식한) Force 알고리즘 : 모든 가능한 경우의 수를 모두 탐색하며 요구 조건에 충족하는 결과만을 가져옴
  • 완전 탐색 알고리즘
  • 주어진 문제를 선형 구조로 구조화 한 후 반복문으로 원하고자 하는 해를 구할 때까지 탐색
  • BFS(너비 우선 탐색)도 브루스 포스 방식의 완전 탐색 알고리즘이다

알고리즘 설계

  • 입력받은 NxN크기의 사탕들을 (N+1)*(N+1)크기의 배열에 넣어준다
    -> 배열의 인덱스 문제를 최소화하기 위해서
  • 사탕 게임을 진행하기 전의 상태가 연속한 사탕 부분의 최대값일 수 있으므로 현재 상태에서의 연속된 사탕의 최대 개수를 구한다
열과 행에 따른 연속되는 항목 개수 카운트 함수
  func SeqMax(row: Int, col: Int) -> Int{
    var temp_count = 1
    var temp_max = 0
    for k in 2...N{
        if board[row][k] != board[row][k-1]{
            temp_count = 1
        }else{
            temp_count += 1
        }
        temp_max = max(temp_max, temp_count)
    }
    
    temp_count = 1
    for k in 2...N{
            if board[k][col] != board[k-1][col]{
                temp_count = 1
            }else{
                temp_count += 1
            }
            temp_max = max(temp_max, temp_count)
        }
    return temp_max
   }
  • 배열의 모든 항목에 접근하면서 다음과 같은 알고리즘을 수행한다
  • 1) 동서남북 인접한 사탕을 확인해서 자신과 다른 블록이면 두 사탕을 교환한다
Tuple을 이용한 이차원 배열의 두 항목 값 교환하기
func changeNum(_ a: (Int, Int), _ b : (Int, Int))  -> (){
    let temp = board[a.0][a.1]
    board[a.0][a.1] = board[b.0][b.1]
    board[b.0][b.1] = temp
}
  • 2) 교환한 이후의 상태에서 연속된 사탕의 개수를 카운트한다
  • 연속된 사탕의 개수 카운트는 어떻게 할까?

  • -> 해당 열과 행을 돌면서 이전 항목과 같은 것일 때 count += 1을 해주고 다른 것일 경우 count 초기화

  • 3) count한 값이 여태까지 구한 해들 중 가장 큰 값일 경우 최대 개수를 업데이트해준다
  • 4) 다음 항목의 알고리즘을 수행을 위해 1에서 바꾼 두 사탕을 다시 교환해준다

swift로 단순 구현 알고리즘을 처음 풀어봤는데 반복되는 부분의 코드들을 함수로 따로 빼서 정의해놓고 최대한 조금 수행하도록 하기 위해 신경을 많이 써서 코드를 짜봤다

전체 코드

import Foundation

let N = Int(readLine()!)!
var board: [[Character]] = Array(repeating: Array(repeating: "." , count: N+2), count: N+2)
for i in 1...N{
    board[i][1...N] = ArraySlice(readLine()!)
}

var candy_max = 0
func changeNum(_ a: (Int, Int), _ b : (Int, Int))  -> (){
    let temp = board[a.0][a.1]
    board[a.0][a.1] = board[b.0][b.1]
    board[b.0][b.1] = temp
}
func SeqMax(row: Int, col: Int) -> Int{
    var temp_count = 1
    var temp_max = 0
    for k in 2...N{
        if board[row][k] != board[row][k-1]{
            temp_count = 1
        }else{
            temp_count += 1
        }
        temp_max = max(temp_max, temp_count)
    }
    
    temp_count = 1
    for k in 2...N{
            if board[k][col] != board[k-1][col]{
                temp_count = 1
            }else{
                temp_count += 1
            }
            temp_max = max(temp_max, temp_count)
        }
    return temp_max
}


for i in 1...N{
    for j in 1...N{
        candy_max = max(candy_max,SeqMax(row: i, col: j))
    }
}

for i in 1...N{
      for j in 1...N{
        //동쪽 확인
        if board[i][j+1] != board[i][j] &&  board[i][j+1] != "."{
            changeNum((i,j), (i,j+1))
            candy_max = max(candy_max,SeqMax(row: i, col: j))
            candy_max = max(candy_max,SeqMax(row: i, col: j+1))
            changeNum((i,j), (i,j+1))
        }
        //서쪽 확인
        if board[i][j-1] != board[i][j] &&  board[i][j-1] != "."{
            changeNum((i,j), (i,j-1))
            candy_max = max(candy_max,SeqMax(row: i, col: j))
            candy_max = max(candy_max,SeqMax(row: i, col: j-1))
            changeNum((i,j), (i,j-1))
        }
        
        //북쪽 확인
        if board[i-1][j] != board[i][j] &&  board[i-1][j] != "."{
            changeNum((i,j), (i-1,j))
            candy_max = max(candy_max,SeqMax(row: i, col: j))
            candy_max = max(candy_max,SeqMax(row: i-1, col: j))
            changeNum((i,j), (i-1,j))
        }
        //남쪽 확인
        if board[i+1][j] != board[i][j] &&  board[i+1][j] != "."{
            changeNum((i,j), (i+1,j))
            candy_max = max(candy_max,SeqMax(row: i, col: j))
            candy_max = max(candy_max,SeqMax(row: i+1, col: j))
            changeNum((i,j), (i+1,j))
        }
    }
}
print(candy_max)