[BOJ] 백준 3085 사탕게임 python

문제

3085번: 사탕 게임

---

 

풀이

인접한 사탕의 색이 다른 경우 서로 위치를 바꿀 수 있고, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)의 사탕을 모두 먹을 수 있는데 먹을 수 있는 사탕의 최대 개수를 구하는 문제이다.

그래프를 for문으로 돌면서 인접한 사탕과 색이 다른 경우 위치를 바꾼다. 그 다음 check() 함수를 실행한다.

check() 함수에서도 그래프를 for문으로 돌면서 인접한 사탕과 색을 비교한다. 색이 같으면 먹을 수 있는 사탕의 최대 개수에 1을 더한다. check() 함수가 끝나면 위치를 바꿨던 사탕의 위치를 원래대로 돌려놓는다.

그래프를 다 탐색을 하면 먹을 수 있는 최대 사탕의 개수를 출력한다.

---

코드

def check(graph):
    global maxCnt

    for i in range(N):

        # 행으로 확인
        cnt = 1
        for j in range(N - 1):
            if graph[i][j] == graph[i][j + 1]:
                cnt += 1
                maxCnt = max(cnt, maxCnt)
            else:
                cnt = 1
    
        # 열로 확인
        cnt = 1
        for j in range(N - 1):
            if graph[j][i] == graph[j + 1][i]:
                cnt += 1
                maxCnt = max(cnt, maxCnt)
            else:
                cnt = 1

N = int(input())
graph = [list(input()) for _ in range(N)]
maxCnt = 0

# 가로로 바꾸면서 확인
for i in range(N):
    for j in range(N - 1):
        if graph[i][j] != graph[i][j + 1]:      # 만약 오른쪽과 다르면?
            graph[i][j], graph[i][j + 1] = graph[i][j + 1], graph[i][j] # 서로 바꾸고
            check(graph)                                                # 확인
            graph[i][j], graph[i][j + 1] = graph[i][j + 1], graph[i][j] # 그리고 다시 돌려놓기

# 세로로 바꾸면서 확인
        if graph[j][i] != graph[j + 1][i]:      # 만약 아래와 다르다면?
            graph[j][i], graph[j + 1][i] = graph[j + 1][i], graph[j][i] # 서로 바꾸고
            check(graph)                                                # 확인
            graph[j][i], graph[j + 1][i] = graph[j + 1][i], graph[j][i] # 그리고 다시 돌려놓기

print(maxCnt)