백준 3085번 사탕 게임 파이썬

리뷰

브루트포스 알고리즘으로 분류되어 있어 for문을 남발했다가 시간 초과를 맞았다, 시간복잡도를 조정하고 제출할때 dist 리스트를 초기화 했던 줄을 지워버려서 NameError까지 떠버렸다... 해당 부분 수정 후 제출 하여 통과하였다.

문제 풀이

n*n 배열을 전체 탐색할 것이기 때문에 방향은 오른쪽과 아래쪽만 탐색할 것이다. (1, 0), (0, 1) 방향 배열 생성

변경할 방향의 좌표값이 n을 벗어나지 않을 경우 서로 내용물을 바꾸어 준다.

별도의 함수를 작성하여 바뀐 리스트를 기준으로 행 및 열을 탐색해 준다.

이전 인덱스와 동일한 사탕일 경우 temp를 올려주고 temp_max를 최신화 해준다. 아닐경우 temp는 1로 초기화

행, 열을 탐색했을때 연속된 사탕의 개수를 return해 준다.

최대 사탕 개수를 최신화 해주고 바꾸었던 내용물을 다시 원상태로 복구시킨다.

n * n 크기의 배열을 모두 돌려준 뒤 연속된 최대 사탕의 갯수 출력

참고 사항

만약 현재 탐색한 행과 열 중에서 n개의 연속된 사탕이 발견됐다면 더이상의 탐색은 필요하지 않다.

정답 코드

def q3085():
    # 백준 3085번 사탕 게임 파이썬
    n = int(input())
    lst = [list(input()) for _ in range(n)]
    dist = [(1, 0), (0, 1)]
    result = 0

    def chk(board):
        x_result = 0
        y_result = 0
        for a in range(n):
            temp = 1
            temp_max = 1
            for b in range(1, n):
                if lst[a][b - 1] == lst[a][b]:
                    temp += 1
                    temp_max = max(temp_max, temp)
                else:
                    temp = 1
            x_result = max(x_result, temp_max)

            temp = 1
            temp_max = 1
            for b in range(1, n):
                if lst[b - 1][a] == lst[b][a]:
                    temp += 1
                    temp_max = max(temp_max, temp)
                else:
                    temp = 1
            y_result = max(y_result, temp_max)
        return max(x_result, y_result)

    for i in range(n):
        for j in range(n):
            for dx, dy in dist:
                ni, nj = i + dx, j + dy
                if ni < n and nj < n:
                    lst[i][j], lst[ni][nj] = lst[ni][nj], lst[i][j]
                    cnt = chk(lst)
                    result = max(result, cnt)
                    lst[i][j], lst[ni][nj] = lst[ni][nj], lst[i][j]
                if result == n:
                    print(n)
                    return
    print(result)
q3085()