3085

날짜 : 2023. 03. 06

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
board = list()
for _ in range(n):
    t = sys.stdin.readline().rstrip()
    temp = list()
    for i in range(len(t)): temp.append(t[i])
    board.append(temp)  # 사탕 입력
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = 0


def candy():  # 먹을 수 있는 사탕 개수 구하기
    cnt = 0
    for i in range(n):
        for j in range(n):
            cur = board[i][j]  # 기준 사탕
            r, c = (i+1), (j+1)
            cnt1, cnt2 = 1, 1
            while r in range(n):  # 아래로
                if board[r][j] == cur:
                    cnt1 += 1
                    r += 1
                else: break
            while c in range(n):  # 오른쪽으로
                if board[i][c] == cur:
                    cnt2 += 1
                    c += 1
                else: break
            cnt = max(cnt, cnt1, cnt2)  # 개수 최신화
    return cnt


for i in range(n):
    for j in range(n):
        for k in range(4):
            x = dx[k] + i
            y = dy[k] + j
            if x in range(n) and y in range(n):
                if board[x][y] != board[i][j]:  # 서로 다른 경우
                    board[x][y], board[i][j] = board[i][j], board[x][y]  # swap
                    res = max(res, candy())  # 개수 구하기
                    board[x][y], board[i][j] = board[i][j], board[x][y]  # 원상복구

print(res)

 

풀이

- 모든 사탕에 대하여 인접사탕이 다른 경우 swap한 후에 먹을 수 있는 사탕의 개수를 구한다.

- 시간 복잡도의 경우 최악의 경우 O(n^4)였지만 n의 크기가 최대 50이기 때문에 1억을 넘지 않아 브루트포스로 가능한 문제였다.

 

 

알게된 점

- 이게 되네...

 

 

참고 사이트

-