[백준/Python] 3085 사탕 게임

 

📌문제 탐색하기

• NxN(3 ≤ N ≤ 50) 크기에 사탕을 채워 놓음
• 사탕의 색이 다른 인접한 두 칸을 골라 고른 칸에 있는 사탕을 서로 교환
• 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행or열)을 골라 그 사탕을 모두 먹음
• 사탕이 채워진 상태가 주어졌을 때, 먹을 수 있는 최대 사탕의 개수 구하기

행방향, 열방향으로 인접한 칸들을 서로 교환해주면서 각 방향에서 같은 색이 연속적으로 놓인 최대 길이를 구해서 최댓값을 갱신하면 모든 칸에 대한 탐색이 끝나고 먹을 수 있는 최대 사탕의 개수를 구할 수 있다.

 

 

---

📌코드 설계하기

1. 보드의 크기 N을 입력받는다.
2. 리스트 candies에 보드에 채워져 있는 사탕의 색상을 입력받는다.
3. 먹을 수 있는 최대 사탕 개수를 저장할 변수 max_candy_cnt를 0으로 초기화한다.
4. 각 칸을 돌면서 오른쪽칸과 교환 / 아래칸과 교환한다.
5. 오른쪽칸과 교환했다면, 해당칸의 열방향을 탐색해서 가장 긴 연속 부분의 개수를 확인하고, 아래칸과 교환했다면 해당칸의 행방향을 탐색해서 가장 긴 연속 부분의 개수를 확인하여 max_candy_cnt를 갱신한다.
6. 모든 칸에 대해 탐색이 종료되면 max_candy_cnt를 출력한다.

 

---

📌정답 코드

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

def get_max_candy_cnt():
    max_candy_cnt = 1
    for i in range(N):
        cnt = 1
        for j in range(1, N):
            if candies[i][j] == candies[i][j-1]:
                cnt += 1
            else:
                cnt = 1
            max_candy_cnt = max(max_candy_cnt, cnt)
        
        cnt = 1
        for j in range(1, N):
            if candies[j][i] == candies[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            max_candy_cnt = max(max_candy_cnt, cnt)
    return max_candy_cnt
    

max_candy_cnt = 0
for i in range(N):
    for j in range(N):
        if i < N-1 and candies[i][j] != candies[i+1][j]:
            candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]
            max_candy_cnt = max(max_candy_cnt, get_max_candy_cnt())
            candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]
        if j < N-1 and candies[i][j] != candies[i][j+1]:
            candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]
            max_candy_cnt = max(max_candy_cnt, get_max_candy_cnt())
            candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]

print(max_candy_cnt)