[백준 / Swift] 3085 - 사탕게임

박준혁 - Niro·2023년 1월 13일
0

백준

목록 보기
9/16
post-thumbnail

🔗 문제 링크


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

💡 문제


상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.

이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

⌨️ 입력


첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

🖨️ 출력


첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

✅ 풀이


해당 배열의 모든 요소를 행과 열 방향으로 요소를 바꾸고 원위치를 시켜야 하기 때문에 처음부터 끝까지 직접 탐색하는 브루트포스 알고리즘 을 사용했습니다.

요소를 바꾸거나 행, 열 중 사탕의 최대 개수를 구하는 알고리즘은 함수로 구현을 했습니다.

swapRow , swapColumn 은 행, 열 방향의 요소를 서로 바꾸는 역할을 하며

sameRow , sameColumn 은 행, 열 방향의 연속된 사탕의 최대 개수를 구하는 역할 입니다.

순서

  1. N x N 의 배열 만들고 요소 입력하기

  2. 행에서 다음 인덱스의 요소와 바꾸고 배열에서 행, 열 중 사탕의 최대 개수 구하기

  3. 바꾼 요소들을 원위치 시키기

  4. 열에서 다음 인덱스의 요소와 바꾸고 배열에서 행, 열 중 사탕의 최대 개수 구하기

  5. 바꾼 요소들을 원위치 시키기

  6. 구한 수 중 가장 큰 수 출력하기

🖥️ 소스 코드


let n = Int(readLine()!)!

var resultRow = [Int]()
var resultColumn = [Int]()

var arr = Array(repeating: Array(repeating: "Z", count: n), count: n)

for i in 0..<n {
    arr[i] = readLine()!.map{ String($0) }
}

for i in 0..<n {
    for j in 0..<n-1 {
        if arr[i][j] == arr[i][j+1] {
            continue
        } else {
            swapRow(i, j)
            resultRow.append(max(sameRow(), sameColumn()))
            swapRow(i, j)
        }
    }
}

for i in 0..<n {
    for j in 0..<n-1 {
        if arr[j][i] == arr[j+1][i] {
            continue
        } else {
            swapColumn(j, i)
            resultColumn.append(max(sameRow(), sameColumn()))
            swapColumn(j, i)
        }
    }
}

print(max(resultRow.max()!, resultColumn.max()!))

func swapRow(_ r: Int, _ c: Int) {
    let temp = arr[r][c]
    arr[r][c] = arr[r][c + 1]
    arr[r][c + 1] = temp
    
}

func swapColumn(_ r: Int, _ c: Int) {
    let temp = arr[r][c]
    arr[r][c] = arr[r + 1][c]
    arr[r + 1][c] = temp
}

func sameRow() -> Int {
    
    var max = 0
    
    for i in 0..<n {
        var same = 1
        for j in 0..<n-1 {
            if arr[i][j] == arr[i][j+1] {
                same += 1
            } else {
                same = 1
            }
            
            if max < same {
                max = same
                
            }
        }
    }
    return max
}

func sameColumn() -> Int {
    
    var max = 0
    
    for i in 0..<n {
        var same = 1
        for j in 0..<n-1 {
            if arr[j][i] == arr[j+1][i] {
                same += 1
            } else {
                same = 1
            }
            
            if max < same {
                max = same
            }
        }
    }
    return max
}
profile
📱iOS Developer, 🍎 Apple Developer Academy @ POSTECH 1st, 💻 DO SOPT 33th iOS Part

0개의 댓글