[백준] 3085번: 사탕 게임 - 파이썬/python

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

접근 방식

- 주어진 사탕 정보 배열에서 연속인 최대 사탕수를 세는 방법 고민

- 사탕의 색이 다른 인접한 두 칸을 서로 교환하는 방법 고민

 

코드 풀이

n = int(input()) # 보드의 크기
candy = [list(input()) for _ in range(n)] # 사탕 색깔 정보

di = [1, 0] # 우하향 방향으로 탐색, 인접 사탕을 바꾸는 데 필요
dj = [0, 1]
answer=0

cnta, cntb = 1, 1 # 가로, 세로의 연속 사탕 개수 count
def check(graph, n):
    global cnta, cntb
    lst = [] # input 그래프의 모든 연속 정보를 저장하는 그래프
    for i in range(n):
        lst.append(cnta)
        lst.append(cntb)
        cnta, cntb = 1, 1
        for j in range(n-1): # j+1 까지가 탐색의 대상이므로 range < n-1
            
            if graph[i][j] == graph[i][j+1]: # 가로로 연속이라면
                cnta += 1 # cnta +1 처리
            else: # 연속이 끊어지면
                lst.append(cnta) # 저장하고
                cnta = 1 # 다시 세기 시작

            if graph[j][i] == graph[j+1][i]: # 세로로 연속이라면
                cntb += 1 # cntb +1 처리   
            else: # 연속이 끊어지면
                lst.append(cntb) # 저장하고
                cntb = 1 # 다시 세기 시작                       
    ans = max(lst)
    return(ans) # 저장된 모든 연속 정보의 최댓값 반환

for i in range(n):
    for j in range(n):
    
        for k in range(2): # graph[i][j] 점을 기준으로 우하향 이동
            if 0 <= i+di[k] < n and 0 <= j+dj[k] < n: # 보드의 크기 이내에서
                if candy[i][j] != candy[i+di[k]][j+dj[k]]: # 우측 or 아래 인접 사탕이 다르다면
                    candy[i][j], candy[i+di[k]][j+dj[k]] = candy[i+di[k]][j+dj[k]], candy[i][j]
                    tmp = check(candy, n) # 위치 변경하고 check
                    if tmp > answer:
                        answer = tmp # check한 값이 정답값보다 큰 경우 업데이트
                    # 다음 탐색을 위해 원상복귀    
                    candy[i][j], candy[i+di[k]][j+dj[k]] = candy[i+di[k]][j+dj[k]], candy[i][j]

print(answer)

코드는 먼저 어떤 종류의 사탕 배열이 이중 리스트 형태로 주어질 때, 같은 맛의 사탕이 연속으로 존재하는 최대값을 반환하는 check 함수를 선언하고, 반복문 안에서 사탕의 위치를 변경해주며, 각각의 배열에서 check 함수를 활용해 조사한 값의 최대값을 구하는 형식으로 이루어집니다.

아래쪽 삼중 for loop를 먼저 살펴보도록 하겠습니다. 처음 두 개의 루프는 배열 graph의 기준이 되는 graph[i][j] 지점을 정하기 위함입니다. 탐색은 우하향 방식으로 이루어지도록 했으므로 세 번째 for loop에서 기준점의 우측 혹은 아래의 사탕을 확인합니다. 사탕의 종류가 다르다면 두 사탕의 위치를 변경하고, check 함수를 활용해 해당 배열에서 최대 연속 사탕의 수를 조사합니다. 이 값이 이전에 조사한 배열에서의 값보다 크다면 정답값으로 업데이트를 해 주며, 이어 탐색을 하기 위해 원래 배열로 원상복귀를 시켜줍니다.

check 함수를 자세히 살펴보겠습니다. check 함수는 배열 그래프와 보드의 크기를 인자로 받습니다. 그리고 가로 방향과 세로 방향의 연속인 사탕 수를 세어 줄 cnta, cntb를 선언합니다. for loop 안에서 가로, 세로 방향으로 연속된 사탕이 나타난다면 cnta, cntb에 +1 처리를 통해 업데이트해주며, 다른 사탕이 나타나는 경우 이전까지의 값을 lst에 저장하고 다시 1로 초기화를 시켜줍니다. 다른 사탕이 나타나 연속이 깨지는 것이 아니라 끝 지점까지 탐색을 완료하여 연속이 중단될 수 있으므로 두 번째 for loop 밖에서 1로 초기화하는 부분을 추가합니다. 현재 지점을 기준으로 인덱스 +1 지점을 탐색하므로 j의 range는 < n-1 까지로 지정했습니다. 

 

오답 이유

check 함수 내에서, 연속이 끝나는 경우는 두 가지가 있습니다. 첫 번째는 다른 종류의 사탕이 나타나는 것이며, 두 번째는 끝 지점까지 탐색을 완료해 모서리에 도착한 경우입니다. 두 번째 경우를 고려하지 못하여 오답이 발생했습니다. (cnta, cntb의 적절한 초기화 시점)

 

메모

서로 다른 인접한 사탕의 위치를 바꾸어 주는 부분에서 현재 지점 대비 모든 방향(상하좌우)의 사탕을 조사할 필요가 없습니다. 기준점 자체를 우하향 방식으로 for loop를 통해 이동시켜주고 있으므로, 동일 조합의 경우에 대해 중복 조사가 이루어지기 때문입니다. 복잡도를 줄이기 위해 상/하 중 하나, 좌/우의 방향 중 하나를 택하여 두 가지 방향으로 조사하면 되며, 위의 코드 풀이에서는 우하향 방식을 활용했습니다.