[백준 알고리즘/Python] 3085 사탕 게임

문제

 

문제 이해

문제 접근이 어려워 다른 사람의 설명을 보았습니다.

중요한 점은

• 사탕을 옮기는 것
• 한 행, 열의 최대값을 구하는 것

 

한 행, 열의 최대값을 구하는 것

행열의 형태로 되어있고 i는 행을 뜻하고 j는 열을 뜻합니다. 3x3의 행열에서는 0부터 시작해 행,열의 끝까지 다른 것이 있다면 swap 해줍니다. 즉, 0행열을 마치면 1의 행열을 swap합니다.

for문이 돌때마다 그림 형태로 같은 것이 있는지 탐색합니다.

 

 

사탕을 옮기는 것

파이썬에서 특별한 swap을 쓰지않고 옮길 수 있습니다.

행이 같을때(가로가 같을때) 양 옆을 바꿉니다. 그리고 다시 돌려놓습니다.

 

코드

import sys
Input = sys.stdin.readline

def count_box(box):
    Max_result = 1

    for i in range(a):

        #열 순회
        count = 1
        for j in range(1,a):
            if(box[i][j] == box[i][j-1]): # 왼쪽, 오른쪽 비교
                count += 1 # 이전 것과 같다면 cnt에 1 더하기
            else:
                count = 1 # 이전과 다르다면 다시 1로 초기화

            if(count > Max_result ):
                Max_result = count

        count = 1        
        for j in range(1, a):
            if(box[j][i] == box[j-1][i]): # 위아래 비교
                count += 1
            else:
                count = 1
            if(count > Max_result ):
                Max_result = count

    return Max_result

a = int(Input())
box = [list(Input()) for _ in range(a) ]
answer = 0

for i in range(a):
    for j in range(a):
        #열 바꾸기(가로)
        if(j+1 < a):
            #인접한것 바꾸기, 같은것도 바꾼다.
            box[i][j], box[i][j+1] =box[i][j+1], box[i][j]
            temp = count_box(box)

            answer = max(temp, answer)

            #다시 돌려놓기
            box[i][j], box[i][j+1] =box[i][j+1], box[i][j]

        #행바꾸기(세로)
        if(i+1 < a):
            #인접한것 바꾸기, 같은것도 바꾼다.
            box[i][j], box[i+1][j] =box[i+1][j], box[i][j]
            temp = count_box(box)
            answer = max(temp, answer)

            #다시 돌려놓기
            box[i][j], box[i+1][j] =box[i+1][j], box[i][j]

print(answer)

각 행, 열을 순회할 때 count를 1로 초기화 하는 이유는 예를 들어 YYYZZ 가 있을 때 Y를 만나면 count는 3이 될것입니다. YZ를 만나는 순간 Z가 2개있으니 Z=2, Y=3으로 새야겠지요.

하지만 Z를 만났을 때 count값을 1로 고치지 않으면 최종 count 값은 4가됩니다. Y를 3개 세고 Z를 셀 때 포함하는 것이죠. 이러면 오류가 납니다. 다른 색을 만났을 때는 초기화를 해야 합니다.