[BAEKJOON/Python] no.3085 사탕게임 | 구현, 브루트포스

문제

---

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

3085번: 사탕 게임

 

1차 풀이 구글링..ㅎ

---

count = int(input())
candy_list = [list(input()) for _ in range(count)]
answer = 0

def check(candy_list):
    answer = 1 

    for i in range(count): #0 1 2
    
        cnt = 1
        for idx in range(1, count): #1 2
            if candy_list[i][idx] == candy_list[i][idx - 1]:
                cnt += 1
            else:
                cnt = 1
            
            if cnt > answer:
                answer = cnt

        cnt = 1
        for idx in range(1, count):
            if candy_list[idx][i] == candy_list[idx - 1][i]:
                cnt += 1
            else:
                cnt = 1

            if cnt > answer:
                answer = cnt
    return answer

for row in range(count):
    for col in range(count):
        if col + 1 < count:
            candy_list[row][col], candy_list[row][col + 1] = candy_list[row][col + 1], candy_list[row][col]
            temp = check(candy_list)

            if temp > answer:
                answer = temp

            candy_list[row][col], candy_list[row][col + 1] = candy_list[row][col + 1], candy_list[row][col]

        if row + 1 < count:
            candy_list[row][col], candy_list[row + 1][col] = candy_list[row + 1][col], candy_list[row][col]
            temp = check(candy_list)

            if temp > answer:
                answer = temp

            candy_list[row][col], candy_list[row + 1][col] = candy_list[row + 1][col], candy_list[row][col]
            
print(answer)

👉🏻먼저 전체 풀이이다.

count = int(input())
candy_list = [list(input()) for _ in range(count)]
answer = 0

• 사탕의 열, 행의 수를 count에 담는다.
• for문을 통해 candy_list에 사탕의 열과 행을 담았다.
• 답을 담을 answer 변수를 만든다.

[['C', 'C', 'P'], ['C', 'C', 'P'], ['P', 'P', 'C']]

👉🏻candy_list의 실제 형태는 다음과 같고

👉🏻편의상 이렇게 표 형태로 보자!

def check(candy_list):
    answer = 1 

    for i in range(count):
    
        cnt = 1
        for idx in range(1, count):
            if candy_list[i][idx] == candy_list[i][idx - 1]:
                cnt += 1
            else:
                cnt = 1
            
            if cnt > answer:
                answer = cnt

        cnt = 1
        for idx in range(1, count):
            if candy_list[idx][i] == candy_list[idx - 1][i]:
                cnt += 1
            else:
                cnt = 1

            if cnt > answer:
                answer = cnt
    return answer

👉🏻check 함수를 이용해 최대로 먹을 수 있는 사탕의 양을 구한다.

• for문을 돌리면서 한 번은 열고정, 한 번은 행고정을 하면서 이전 사탕과의 색깔을 비교한다.

for row in range(count):
    for col in range(count):
        if col + 1 < count:
            candy_list[row][col], candy_list[row][col + 1] = candy_list[row][col + 1], candy_list[row][col]
            temp = check(candy_list)

            if temp > answer:
                answer = temp

            candy_list[row][col], candy_list[row][col + 1] = candy_list[row][col + 1], candy_list[row][col]

        if row + 1 < count:
            candy_list[row][col], candy_list[row + 1][col] = candy_list[row + 1][col], candy_list[row][col]
            temp = check(candy_list)

            if temp > answer:
                answer = temp

            candy_list[row][col], candy_list[row + 1][col] = candy_list[row + 1][col], candy_list[row][col]

• for문을 돌리면서 사탕의 자리를 바꾸어준다.
• 사탕의 자리를 바꾼 상태의 candy_list를 check함수에 넣어준다.
• 함수에서 return된 값을 answer와 비교해 더 크다면 answer값을 갱신해준다.
• 다시 사탕의 자리를 원위치시켜준다.