백준 3085번 사탕 게임 | python | 브루트포스

Konseo·2023년 8월 17일
0

코테풀이

목록 보기
9/59

문제

링크

풀이

문제 한 줄 한 줄을 그대로 코드화 시키면 되는 구현 문제이다. 처음엔 그래프 알고리즘으로 풀 수 있을까 싶어 고민하다가, 그냥 완탐으로 풀었다.
4중 for문이 들어가긴 하지만 가능한 n의 최댓값이 50이므로 50^4 < 2000만이라 충분할 것이라 생각했기 때문이다. (그치만 처음엔 시간초과가 났음, 어떻게 맞췄는 지는 아래에서 설명)

먼저, 우리는 사탕의 색이 다른 인접한 두 칸을 골라 이 둘을 교환할 것이다.

인접한 두 칸을 고를 땐 현재 칸을 기준으로 오른쪽 칸과 아래쪽 칸이랑만 교환해보면 된다. 사탕 정보가 저장된 리스트를 c라고 할 때, c[0][0]에서부터 순차적으로 검사할 것이기 때문에 왼쪽 칸과 위쪽 칸을 중복으로 검사해 볼 필요가 없다. 교환은 말그대로 두 변수 값을 swap해주면 된다.

여기서 고려해볼 점은 오른쪽 칸의 인덱스와 아래쪽 칸 인덱스가 정상 범위 내에 있는지, 그리고 swap할 두 사탕이 서로 다른 지(같으면 swap하는 의미가 없으므로) 확인해보아야한다. 본인은 두 사탕이 서로 다른 지 조건을 추가해서 시간초과를 피해갈 수 있었다 😄

그 다음, 교환으로 인해 갱신된 c에 대하여 모두 같은 색으로 이루어진 가장 긴 부분을 확인한다. 현재 c에 대한 최대길이값을 직관적으로 알아보기 위해 checkCurMaxNum()로 함수화하였다. 여기서 고려할 점은 행 기준 최댓값과 열 기준 최댓값을 모두 확인해보아야한다는 것이다.

위 과정을 모든 c의 원소(사탕)에 대하여 순차적으로 검사해보면 된다. 참고로 swap해 둔 칸은 다시 원상복구 해두어야 하기 때문에 checkCurMaxNum() 수행 후 다시 한 번 swap해주어야 함을 잊지 말자 !

import sys

input = sys.stdin.readline
n = int(input())
c = [list(input()) for _ in range(n)]

# 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다.
# 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.
# 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음
# 그 사탕을 모두 먹는다.


def checkCurMaxNum():
    max_cnt = 1  # total_max_cnt
    for i in range(n):
        # 가로 먼저 확인
        cnt = 1
        for j in range(1, n):
            if c[i][j] == c[i][j - 1]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
        # 세로 확인
        cnt = 1
        for j in range(1, n):
            if c[j][i] == c[j - 1][i]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)

    return max_cnt


# 오른쪽 swap, 아래쪽 swap
result = 1
for i in range(n):
    for j in range(n - 1):
        # 오른쪽 swap
        if j + 1 < n and c[i][j] != c[i][j + 1]:
            c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j]  # swap
            # 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고름
            result = max(result, checkCurMaxNum())
            c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j]  # 다시 되돌리기
        # 왼쪽 swap
        if i + 1 < n and c[i][j] != c[i + 1][j]:
            c[i][j], c[i + 1][j] = c[i + 1][j], c[i][j]  # swap
            # 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고름
            result = max(result, checkCurMaxNum())
            c[i][j], c[i + 1][j] = c[i + 1][j], c[i][j]  # 다시 되돌리기

print(result)
profile
둔한 붓이 총명함을 이긴다

0개의 댓글