[알고리즘|파이썬] 백준 3085 사탕 게임

문제 링크: https://www.acmicpc.net/problem/3085

📌 문제 탐색하기

시간 제한: 1초
메모리 제한: 128 MB

 

📌 풀이하기 

예제 1.

3
CCP
CCP
PPC

비교할 대상을 골라 자리 교환을 한 후, 최대 길이가 얼마인지 확인을 한다.

---

📌 코드 설계하기

1. input을 받는다

2. 교환할 대상을 찾아 교환을 한다.

  - 가로 교환

  - 세로 교환

3. 최대 길이가 얼마인지 확인한다.

4. 전체 경우의 수 중 최대 길이를 출력한다.

---

📌 정답 코드

n = int(input())
nmap = [[0 for _ in range(n)] for _ in range(n)]
max_count = 0


def check_count():
    max_row_count = 0
    for i in range(n):
        row_count = 1
        for j in range(n - 1):
            if nmap[i][j] == nmap[i][j + 1]:
                row_count += 1
                if j == n-2:
                    max_row_count = max(row_count, max_row_count)
            else:
                max_row_count = max(row_count, max_row_count)
                row_count = 1
    max_col_count = 0
    for i in range(n):
        col_count = 1
        for j in range(n - 1):
            if nmap[j][i] == nmap[j + 1][i]:
                col_count += 1
                if j == n-2:
                    max_col_count = max(max_col_count, col_count)
            else:
                max_col_count = max(max_col_count, col_count)
                col_count = 1
    count = max(max_row_count, max_col_count)
    return count


for i in range(n):
    line = input()
    for j in range(n):
        nmap[i][j] = line[j]

# 가로 교환
for i in range(n - 1):
    for j in range(n):
        if nmap[j][i] != nmap[j][i + 1]:
            # 00 01 / 10 11 / 20 21
            old_a = nmap[j][i]
            old_b = nmap[j][i + 1]
            nmap[j][i] = old_b
            nmap[j][i + 1] = old_a
            now = check_count()
            max_count = max(now, max_count)
            nmap[j][i] = old_a
            nmap[j][i + 1] = old_b

# 세로 교환
for j in range(n):
    for i in range(n - 1):
        if nmap[i][j] != nmap[i + 1][j]:
            # 00 10 / 10 20 / 01 11
            old_a = nmap[i][j]
            old_b = nmap[i + 1][j]
            nmap[i][j] = old_b
            nmap[i + 1][j] = old_a
            now = check_count()
            max_count = max(now, max_count)
            nmap[i][j] = old_a
            nmap[i + 1][j] = old_b


print(max_count)