파이썬 코테 : 백준 3085 (브루스포스)

문제

사탕 게임 성공출처다국어분류
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16057 4939 3534 30.595%
문제

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

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

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

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

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

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

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

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 1

4

힌트

4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 1번

데이터를 추가한 사람: 10jobss, sanhaehong
문제를 번역한 사람: baekjoon
문제의 오타를 찾은 사람: jh05013
잘못된 조건을 찾은 사람: juhyun16

알고리즘 분류

구현
브루트포스 알고리즘

해석

i) 그냥 행의 최대 인접 개수와 열의 최대 인접 개수 구하는 함수 만들기
ii) 오른쪽 원소와 바꿔주기, 왼쪽 원소와 바꿔주기를 맨 오른쪽 열이랑 맨 아래쪽 열 빼고 실행
iii) 마지막에 최우측 열 원소들을 아래방향으로 바꿔주고 최하측 행 원소들을 오른쪽 방향으로 바꿔주기

풀이