[Python] 백준 3085번 - 사탕 게임 (실버2)

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

3085번: 사탕 게임

 

 

혼자 힘으로 풀었는가? O
(반례 참고)
알고리즘 분류
 - 구현
 - 브루트포스 알고리즘

 

문제

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

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

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

입력

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

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

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

출력

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

 

 

---

 

가로와 세로의 문자를 바꿔서 가장 긴 연속되는 행과 열을 찾는 문제이다.

 

하나하나 바꿔가며 모든 경우의 수를 찾으면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
data = []
for i in range(n):
    data.append(list(input().rstrip()))
    
result = 0

dx = [1, 0]
dy = [0, 1]
# 0,0부터 n-1, n-1 까지 순차적으로 내려가기 때문에 우측과 아래측만 바꿔서 비교하면 전부 확인

def get_count(x, y):
    cnt_x = 0
    cnt_y = 0
    #주어진 좌표에서 연속되는 문자열 찾기
    for i in range(x, n):
        if data[x][y] == data[i][y]:
            cnt_x += 1
        else:
            break
    for i in range(x-1, 0-1, -1):
        if data[x][y] == data[i][y]:
            cnt_x += 1
        else:
            break
            
    for i in range(y, n):
        if data[x][y] == data[x][i]:
            cnt_y += 1
        else:
            break
    for i in range(y-1, -1, -1):
        if data[x][y] == data[x][i]:
            cnt_y += 1
        else:
            break
    return max(cnt_x, cnt_y)


for i in range(n):
    for j in range(n):
        for k in range(2):
            nx = i+dx[k]
            ny = j+dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                data[i][j], data[nx][ny] = data[nx][ny], data[i][j] #바꾸기
                result = max(result, get_count(i, j), get_count(nx, ny))
                if result == n: #최대이므로 종료
                    print(n)
                    exit()
                data[i][j], data[nx][ny] = data[nx][ny], data[i][j] #원래대로 돌리기
                
print(result)

약간.. 단순 무식해 보인다.

 

검색해서 다른사람의 코드도 좀 보았는데 접근법 자체는 크게 다를 게 없는 것 같다.