3085번: 사탕 게임

3085번: 사탕 게임

 

사탕 게임 

 

문제

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

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

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

입력

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

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

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

출력

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

예제 입력 1 

3
CCP
CCP
PPC

예제 출력 1 

3

 

---

풀이

문제를 이해해보자.

1. N*N 크기에 사탕이 채워져있다.
2. 사탕의 색이 다른 인접한 칸이라면 교환할 수 있다.
3. 사탕의 색은 4가지이다. (빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y)
4. 같은 사탕색으로 이루어진 행과 열 중에서 최대 사탕 개수를 구해라.

 

행과 열을 탐색하는데 다른 색이 인접한 위치라면 교환도 가능해야 한다. 

교환이 가능해야 한다는게 어려웠다. 교환 전과 교환 후에 사탕 개수를 구해 더 큰 값이 있는지 판단해야 하는데 이걸 어떻게 구할지 감이 안잡혔다. 

 

 

처음에 생각한 방법은,

 

1. 탐색 방법 

 

모든 경우의 수를 다 탐색하는 것이었다. 하지만 이 방법은 문제가 있었다.

예제 1과 같은 경우를 생각해봐도 경우의 수가 너무 많다. 시간 복잡도에 걸릴 것이 분명하다.

 

2. 사탕 개수 

 

사탕이 4가지이니 4크기의 배열을 만들어 그 값을 증가시키려고 했다. 색상 순서대로 0,1,2,3 이렇게 두어 탐색 도중 해당 색을 만나면 그 값을 1씩 증가시키려고 했다. 색상을 굳이 나눠서 값을 증가시킬 필요가 있을까?

 

---

설계

처음 생각한 방법에서 좀 더 발전시켜 생각을 해보자.

 

1. 탐색 방법

 

모든 경우의 수를 탐색하는 데에 많은 시간이 소요되니, 다르게 생각을 해보자.

문제에서 행과 열에서 같은 색을 가진 최대 사탕 개수를 구하라고 했다.

다른 모든 위치를 탐색할 필요없이 해당 위치에서 행과 열을 비교하며 최대 사탕 개수를 구하면 된다.

 

2. 사탕 교환

 

사탕 개수를 생각하기 전, 인접한 위치에서 다른 색일 때 교환하는 경우를 생각해보자.

해당 위치에서 인접한 위치인 곳에 다른 색이라면 모두 교환을 해줘야 한다.

인접한 위치에서 교환하는 경우는 아래쪽, 오른쪽 두 가지이다.

 

• 아래쪽
• 오른쪽

 

3. 사탕 개수

 

사탕을 교환하고 난 뒤 해당 위치의 행과 열을 탐색하며 최대 사탕 개수를 구한다.

색상을 나눌 필요없이 cnt 값 하나로 max 값을 바꾸며 탐색할 수 있을 것 같다.

cnt 값 하나로 판단하기 위해 열 탐색과 행 탐색을 나눠서 탐색해야 한다.

 

• 열 탐색
• 행 탐색

 

 

 

---

구현

 

위의 설계를 바탕으로 코드를 구현해보자.

 

1. 사탕 교환

사탕 교환은 오른쪽과 아래쪽 두 경우에만 교환이 가능하면 교환하여 사탕 개수를 판단하고 난 뒤에 다시 원래 위치로 돌려줘야 한다.

 

1) 오른쪽 

 

2) 아래쪽

 

 

2. 사탕 개수

 

1) 열 탐색

 

 

2) 행 탐색

 

 

---

전체코드

 

let N = Int(readLine()!)!

var arr : [[String]] = []

var maxValue = 0

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

    arr.append(Input)
}

for i in 0..<N{
    for j in 0..<N-1{
        var swap = arr[i][j]
        arr[i][j] = arr[i][j+1]
        arr[i][j+1] = swap
        
        search()
        swap = arr[i][j]
        arr[i][j] = arr[i][j+1]
        arr[i][j+1] = swap
    }
}
for i in 0..<N{
    for j in 0..<N-1{
        var swap = arr[j][i]
        arr[j][i] = arr[j+1][i]
        arr[j+1][i] = swap
        
        search()
        swap = arr[j][i]
        arr[j][i] = arr[j+1][i]
        arr[j+1][i] = swap
    }
}


func search(){
    for i in 0..<N{
        var cnt = 1
        for j in 0..<N-1{
            if(arr[i][j] == arr[i][j+1]){
                cnt+=1
            }
            else{
                cnt = 1
            }
            maxValue = max(maxValue, cnt)
                
        }
    }
    
    for i in 0..<N{
        var cnt = 1
        for j in 0..<N-1{
            if(arr[j][i] == arr[j+1][i]){
                cnt+=1
            }
            else{
                cnt = 1
            }
            maxValue = max(maxValue, cnt)
                
        }
    }
}

print(maxValue)