🥚문제링크

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

• 구현
• 브루트포스 알고리즘

---

🍳코드

import sys
input = sys.stdin.readline


def count(arr):
    # 가장 긴 행 또는 열의 연속 부분을 구한다
    max_cnt = 0

    # 행
    for row in range(N):
        prev = arr[row][0]
        cnt = 1
        for col in range(1, N):
            if arr[row][col] == prev:
                cnt += 1
            else:
                cnt = 1  # reset
                prev = arr[row][col]

            # 현재까지의 cnt가 max_cnt보다 크면 갱신
            max_cnt = max(max_cnt, cnt)

    # 열
    for col in range(N):
        prev = arr[0][col]
        cnt = 1
        for row in range(1, N):
            if arr[row][col] == prev:
                cnt += 1
            else:
                cnt = 1  # reset
                prev = arr[row][col]

            # 현재까지의 cnt가 max_cnt보다 크면 갱신
            max_cnt = max(max_cnt, cnt)

    return max_cnt


N = int(input().strip())
arr = [list(input().strip()) for _ in range(N)]  # 사탕이 채워진 상태

# 아래쪽, 오른쪽만 검사하면 된다
# e.g., (r, c)와 그 우측을 교체한 것 = (r, c+1)과 그 좌측을 교체한 것
dr = [0, 1]
dc = [1, 0]

max_ans = 0

for r in range(N):
    for c in range(N):
        for i in range(2):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                # 사탕의 색이 다른 인접한 두 칸을 고른다
                if arr[r][c] != arr[nr][nc]:
                    # 교체
                    arr[r][c], arr[nr][nc] = arr[nr][nc], arr[r][c]
                    # 카운트
                    max_ans = max(max_ans, count(arr))
                    # 교체
                    arr[r][c], arr[nr][nc] = arr[nr][nc], arr[r][c]

print(max_ans)

---

🧂아이디어

구현, 브루트포스

• 인접한 부분을 탐색할 때, 상, 하, 좌, 우를 다 탐색할 필요 없이 아래쪽과 오른쪽만 탐색 하면 시간초과를 해결할 수 있다.

• (r, c)와 그 우측을 교체한 상태 = (r, c+1)과 그 좌측을 교체한 상태

• 교체를 한 뒤, 가장 긴 연속부분을 카운트해주고, 다시 교체를 해서 원래 arr 상태로 되돌려야 한다.

---

💭

으아아 빡대가리
세세한 부분에서 실수한 것 때문에 계속 '틀렸습니다' 가 떴다. (결과는 사소하지 않지만)
count 함수의 이중 for문의 inner의 끝에서 max_cnt를 계속 갱신해줘야 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 구할 수 있는데, 실수로 이중 for문의 inner for문을 빠져나온 뒤에 max_cnt를 갱신해줬기 때문에 값이 올바르게 구해지지 않았다.