[Baekjoon] 백준 3085 '사탕 게임' 문제풀이 Python, 파이썬, 알고리즘 정리

 

📝 3085 문제 

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력 

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

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

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

 

 

출력

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

 

🧐 풀이

이 문제는 완전탐색 문제이다. 

인접한 다른 두 칸을 고른 후 서로 교환하는 조건은 파이썬의 swap을 사용해서 해결할 수 있다. 

candy_count() 함수

처음에는 row와 col의 cnt, max를 모두 나눠서 계산했는데 시간초과가 나와 합쳐서 구하는 방법으로 방향을 틀었다. 

- row와 col의 기준을 나눠 반복문 안의 조건문을 다르게 설정하고 색이 같다면 cnt를 1씩 증가시켰다.

- max_cnt값을 구해 반환하도록 하였다. 

 

- N과 보드 안의 문자들을 입력받고 조건을 따져 swap을 한다.

- 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른 후 다시 되돌린다. 

- 되돌릴 때에도 swap을 사용했다.

 

 

 

def candy_count() :
    cnt, max_cnt = 1, 1
    res = 0 
    
    for i in range(N) :
        cnt = 1
        #행 기준 탐색
        for j in range(1, N) :
            if board[i][j] == board[i][j-1] :   #인접한 보드와 색이 같다면 
                cnt += 1
            else :
                cnt = 1
            max_cnt = max(max_cnt, cnt)

    
        #열 기준 탐색 
        for j in range(1, N) :
            if board[j][i] == board[j-1][i] :   #인접항 보드와 색이 같다면 
                cnt += 1
            else :
                cnt = 1
            max_cnt = max(max_cnt, cnt)

    
    res = max(max_cnt, cnt)
    return res   


N = int(input())
board = [list(input()) for _ in range(N)]

res = 1
for i in range(N) :
    for j in range(N-1) :
        if j+1 < N and board[i][j] != board[i][j+1] :
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            res = max(res, candy_count())
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
        if i+1 < N and board[i][j] != board[i+1][j] :
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            res = max(res, candy_count())
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            
        
print(res)