[백준][Python] 3085 사탕 게임

구현, 브루트포스 / 실버 2

🍬

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

3085번: 사탕 게임

 

내 풀이

import copy

def change(x, y):
    result = 1

    for k in range(2):
        cx = x + dx[k]
        cy = y + dy[k]

        if 0 <= cx < N and 0 <= cy < N and candy[x][y] != candy[cx][cy]: # 범위 내에 있으면서 서로 다른 색의 사탕인 경우
            num = 1
            temp = copy.deepcopy(candy)
            temp[cx][cy], temp[x][y] = temp[x][y], temp[cx][cy]

            for a in range(N):
                # 행 검사
                current = temp[a][0]
                num = 1
                for b in range(1, N):
                    if current == temp[a][b]:
                        num += 1
                        result = max(result, num)
                    else:
                        current = temp[a][b]
                        num = 1

                # 열 검사
                current = temp[0][a]
                num = 1
                for b in range(1, N):
                    if current == temp[b][a]:
                        num += 1
                        result = max(result, num)
                    else:
                        current = temp[b][a]
                        num = 1

    return result

N = int(input())

candy = [[] * N for _ in range(N)]
ans = 1

dx = [1, 0]
dy = [0, 1]

for i in range(N):
    candy[i] = list(input())

for i in range(N):
    for j in range(N):
        ans = max(ans, change(i, j))

print(ans)

 

 

 

코드 설명

ans: 정답 변수. 인접한 사탕이 없더라도 무조건 하나(자기 자신)는 먹을 수 있으므로 1로 초기화.

dx, dy: 이동 좌표. 상하좌우를 검사하면, 불필요한 중복이 발생한다. 오른쪽과 아래만 검사하도록 설정.

ans = 1
dx = [1, 0]
dy = [0, 1]

 

모든 좌표를 검사하면서, 먹을 수 있는 사탕의 최대 개수(ans)를 갱신한다.

for i in range(N):
    for j in range(N):
        ans = max(ans, change(i, j))

 

 

✔️ change 함수

 

num: 같은 색의 인접한 사탕 개수

새 좌표가 범위 내에 있으면서 서로 다른 색의 사탕인 경우 num = 1로 설정하고,

원본 값을 변경하지 않기 위해 candy의 값을 복사하여 temp를 생성한 후, 두 개의 사탕을 바꾸어주었다.

원본값을 변경했다가 다시 돌려놓는 방식으로 진행해도 된다.

if 0 <= cx < N and 0 <= cy < N and candy[x][y] != candy[cx][cy]: # 범위 내에 있으면서 서로 다른 색의 사탕인 경우
    num = 1
    temp = copy.deepcopy(candy)
    temp[cx][cy], temp[x][y] = temp[x][y], temp[cx][cy]

 

전체 행과 열을 검사한다.

같은 색의 사탕이 연속되고 있다면 num 값을 증가한다.

그렇지 않은 경우, num를 다시 1로 설정한다.

리턴할 값인 result에는 이때까지 나온 num 중에 가장 큰 값이 들어가게 된다.

for a in range(N):
    # 행 검사
    current = temp[a][0]
    num = 1
    for b in range(1, N):
        if current == temp[a][b]:
            num += 1
            result = max(result, num)
        else:
            current = temp[a][b]
            num = 1

    # 열 검사
    current = temp[0][a]
    num = 1
    for b in range(1, N):
        if current == temp[b][a]:
            num += 1
            result = max(result, num)
        else:
            current = temp[b][a]
            num = 1

 

 

 

🙀 어려웠던 점

 

어떻게 풀어야할지 감이 잘 안 잡혔다.

모든 행과 열을 다 검사하는 방식이 아닌 최선의 방식을 찾아보려 했지만, 결국은 다 검사하는 수밖에,,

 

시간 초과가 발생했었는데, 다음과 같이 수정하니 통과되었다.

 

1. 행과 열을 검사할 때, 각각 for문을 돌리고 있었다. ➡ 하나로 합쳤다.

2. 현재 좌표의 상하좌우를 모두 검사하였다. ➡ 오른쪽과 아래만 검사하도록 수정하였다.