[백준] 3085번 사탕게임

출처: [백준] 3085번 사탕게임

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	17749	5491	3869	30.534%

---

문제

상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

---

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

---

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

---

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

---

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 1번
  • 데이터를 추가한 사람: 10jobss, sanhaehong
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013
  • 잘못된 조건을 찾은 사람: juhyun16

---

알고리즘 분류

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

---

소스코드

import sys

input = sys.stdin.readline


def check(arr):
    n = len(board)
    answer = 1
    for i in range(n):
        cnt = 1
        for j in range(1, n):  # 열 순회하면서 연속 숫자 세기
            if arr[i][j] == arr[i][j - 1]:  # 이전것과 같으면 cnt+1
                cnt += 1
            else:  # 이전 것과 다르면  cnt=1 초기화
                cnt = 1
            if cnt > answer:
                answer = cnt

        cnt = 1
        for j in range(1, n):  # 행 순회하면서 연속 숫자 세기
            if arr[j][i] == arr[j - 1][i]:  # 이전것과 같으면 cnt+1
                cnt += 1
            else:  # 이전 것과 다르면  cnt=1 초기화
                cnt = 1
            if cnt > answer:
                answer = cnt

    return answer


N = int(input())
board = [list(input().rstrip()) for _ in range(N)]
result = 0

for i in range(N):
    for j in range(N):
        if j + 1 < N:  # 열 체크
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]  # 인접 교환
            temp = check(board)
            if temp > result:
                result = temp
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]  # 원복

        if i + 1 < N:  # 행 체크
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]  # 인접 교환
            temp = check(board)
            if temp > result:
                result = temp
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]  # 원복

print(result)