[알고리즘 문제] 가장 긴 바둑돌 (Python / 파이썬)

문제

유니가 바둑돌 게임을 하려고 한다.
바둑돌의 색상은 빨강색(R), 초록색(G), 파란색(B), 노랑색(Y)이다.
처음에 NxN의 크기의 정사각형 바둑판에 바둑돌을 채워놓는다. 바둑돌의 색은 모두 같지 않을 수 있다.유니가 상하좌우의 방향 중 바둑돌의 색이 다른 인접한 두 칸을 골라 두 개의 위치를 바꾼다.이 상황에서 가로 혹은 세로 방향으로 모두 같은 색으로 이루어진 가장 긴 길이의 바둑돌을 가져갈 수 있다.
바둑돌이 채워진 상태가 주어졌을 때, 유니가 가져갈 수 있는 바둑돌의 최대 개수를 구하는 프로그램을 작성하시오

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다.
각 테스트케이스의 두번째 줄부터 N줄에 걸쳐 바둑판의 상태가 공백 없이 주어진다.
( 1 ≤ T ≤ 10, 3 ≤ N ≤ 50 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니가 가져갈 수 있는 바둑돌의 최대 개수를 출력한다.

---

문제 풀이

이전에 백준에서 똑같은 문제를 푼 적이 있는데

그때와 똑같은 이유로 문제를 틀리고 말았다ㅠㅠ 

앞으로는 코드를 좀 더 꼼꼼히 분석해야겠다..!

 

먼저, 상하좌우의 방향 중 바둑돌의 색이 다른 두 칸을 골라 두 개의 위치를 바꾼다.

바꾼 뒤 가로 혹은 세로 방향으로 모두 같은 색으로 이루어진 가장 긴 길이의 바둑돌을

가져갈 수 있는데, 이때 가져 갈 수 있는 바둑돌의 최대 개수를 구하는 문제이다.

 

바둑돌을 상하좌우 방향으로 바꿔보면, 결국 오른쪽과 아래의 위치로만 바꾸면 된다는 것을

쉽게 확인할 수 있다. (그림을 그려보면 명확하게 보임!)

따라서, 바둑돌의 모든 위치를 확인하며 오른쪽과 아래에 색이 다른 바둑돌이 있으면 위치를 바꿔준다.

위치를 바꿔 준 뒤 유니가 얻을 수 있는 바둑돌의 최대 개수를 계산해준다. 

계산 해 준 뒤 바꾼 바둑돌의 위치는 다음 탐색을 위해 원상복구 해줘야 한다. 

 

바둑돌의 최대 개수를 구하는 방법은 간단하다. 

각 열과 행에서 연속된 바둑돌이 있다면 개수를 세어주면 된다. 

이때 주의해야할 점은 다른 색의 바둑돌이 나오면 개수를 초기화 해줘야 한다는 것이다. 

그리고 최대값을 그때그때마다 갱신해줘야한다는 점이다.

만약 그때마다 갱신해주지 않으면 GGGYY 같은 문자열이 있다고 할 때 

맨 마지막에 count는 결국 2 가 되므로 최대값인 3을 구할 수 없다. 

---

My Code

# 바둑돌의 최대 개수를 구하는 함수
def get_score():
    max_count = 0
    # 각 행에서 최대 개수 찾아줌 
    for i in range(n):
        count = 1
        for j in range(n - 1):
            if array[i][j] == array[i][j + 1]: # 연속 된 색이라면
                count += 1 # 개수 세어줌
            else: # 다른 색이 나오면
                count = 1 # 개수 초기화
            max_count = max(max_count, count) # 최대 값 계산해줌

    # 각 열에서 최대 개수 찾아줌 
    for j in range(n):
        count = 1
        for i in range(n - 1):
            if array[i][j] == array[i + 1][j]: # 연속 된 색이라면
                count += 1 # 개수 세어줌
            else: # 다른 색이 나오면
                count = 1 # 개수 초기화
            max_count = max(max_count, count) # 최대 값 계산해줌
    
    return max_count 

for tc in range(int(input())):
    n = int(input()) # 바둑판의 크기

    array = []
    for _ in range(n):
        array.append(list(input())) # 바둑돌의 색상 정보
    
    result = 0
    for i in range(n):
        for j in range(n):
            # 아래쪽으로 탐색, 색이 다르다면 
            if i < n - 1 and array[i][j] != array[i + 1][j]:
                array[i][j], array[i + 1][j] = array[i + 1][j], array[i][j] # 위치 바꿈
                result = max(result, get_score()) # 바꾼 뒤 최대 개수 계산
                array[i][j], array[i + 1][j] = array[i + 1][j], array[i][j] # 원상복구
            # 오른쪽으로 탐색, 색이 다르다면
            if j < n - 1 and array[i][j] != array[i][j + 1]:
                array[i][j], array[i][j + 1] = array[i][j + 1], array[i][j] # 위치 바꿈
                result = max(result, get_score()) # 바꾼 뒤 최대 개수 계산
                array[i][j], array[i][j + 1] = array[i][j + 1], array[i][j] # 원상복구

    print('#' + str(tc + 1), end = ' ')
    print(result)