[백준/브루트포스] 3085번 사탕 게임

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

3085번: 사탕 게임

 

[풀이 방법]

 

1. BFS처럼 하나의 점(A)와 각 위,아래,오른쪽,왼쪽 방향 색에서 다른 지점(B)을 확인해서

2. A, B를 서로 바꾸고

3. 연속된 것의 최대 길이를 확인하기

4. A, B를 바꿔서 원래대로 돌려놓기.

 

위의 과정을 반복하는 것으로 생각했다.

 

그런데 위에서 순차적으로 내려오면서 확인하므로, 4 방향을 확인할 필요 없이 아래와 오른쪽만 확인하면 된다.

 

1. BFS처럼 하나의 점(A)와 각 아래,오른쪽 방향 색에서 다른 지점(B)을 확인해서

2. A, B를 서로 바꾸고

3. 연속된 것의 최대 길이를 확인하기

4. A, B를 바꿔서 원래대로 돌려놓기.

 

import sys

input = sys.stdin.readline

#가장 긴 연속 부분 확인
def check(N, M):
    global ans
    for i in range(N): #행 확인
        cnt = 1
        for j in range(N-1):
            if M[i][j] == M[i][j+1]:
                cnt += 1
                ans = max(cnt,ans)
            else:
                cnt = 1
    for i in range(N): #열 확인
        cnt = 1
        for j in range(N-1):
            if M[j][i] == M[j+1][i]:
                cnt += 1
                ans = max(cnt, ans)
            else:
                cnt = 1
                
ans = 1
N = int(input())
Map = [list(input()) for _ in range(N)]

for i in range(N):
    for j in range(N):
        #열바꾸기
        if j+1 < N:
            Map[i][j], Map[i][j+1] = Map[i][j+1],Map[i][j]
            check(N,Map)
            Map[i][j], Map[i][j+1] = Map[i][j+1], Map[i][j]

        #행바꾸기
        if i+1 < N:
            Map[i][j], Map[i+1][j] = Map[i+1][j], Map[i][j]
            check(N,Map)
            Map[i][j], Map[i+1][j] = Map[i+1][j], Map[i][j]
print(ans)