문제

문제 이해

처음 문제를 봤을때, 이 문제는 브루트포스로 풀 수 있다고 생각했고 그게 맞았다. 그런데 구현력과 세부적인 로직을 떠올리지 못해서 스스로 풀지를 못 했다. 문법적으로 잘 몰라서 그렇기도 하고, 코드가 약간 시뮬레이션 + 브루트포스라서 머릿속에서 여러 생각이 섞여서 그런 것도 같다.

일단 N과 2차원리스트를 받는다. 좌표를 하나씩 돌아가면서 상하좌우로 바꿀 수 있는지 확인한다. 바꿀 수 있다는 건 ny, nx가 범위 안의 값이면서 바꿀 문자가 현재 문자와 달라야 한다. 바꿀 두 문자가 같으면 의미가 없기 때문이다. 이 조건을 모두 통과하면 두 문자의 위치를 바꾸고, 행과 열을 확인해서 같은 종류의 캔디의 최댓값을 구하고 다시 두 문자를 원위치 시킨다. 근데 이게 구현하기가 은근 어렵다.

근데 난 이 문제 체감 난이도가 실버 2보다 높다. 직전 게시글인 "체스판 다시 칠하기"도 그랬다.

코드

# 백준 3085번 사탕 게임

# Function finding max_value
def find_max():
    global N, board

    # row 행
    max_value1 = 0 # 행행에서의 최댓값을 저장할 변수

    for i in range(N):
        c = "V" # 직전 문자 저장 변수. 그래서 board에는 없는 값으로 초기값을 설정
        cnt = 0
        for j in range(N):
            if board[i][j] == c: # 이전 문자와 같다면 원래 카운트에서 1증가
                cnt += 1
            else: # 이 문자가 직전에 없었으면 카운트는 1
                cnt = 1
                c = board[i][j] # 방금 나온 문자를 저장    
            
            max_value1 = max(max_value1, cnt)

    # column 열
    max_value2 = 0 # 열에서의 최댓값을 저장할 변수

    for i in range(N):
        c = "V" # 직전 문자 저장 변수. 그래서 board에는 없는 값으로 초기값을 설정
        cnt = 0
        for j in range(N):
            if board[j][i] == c:
                cnt += 1
            else:
                cnt = 1
                c = board[j][i] # 방금 나온 문자를 저장
            
            max_value2 = max(max_value2, cnt)
    
    return max(max_value1, max_value2)

# input
N = int(input())
board = [list(input()) for _ in range(N)]

# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

max_value = 0 # 최댓값을 넣어서 출력할 변수수

# 이중 반복문은 좌표를 하나씩 돌아가기 위해
for y in range(N):
    for x in range(N):
        
        for i in range(4): # 상하좌우 확인을 위해
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N: # 범위를 벗어나지 않는지 체크
                if board[y][x] != board[ny][nx]: # 옮길 값이라 바꿀 값이 다를때만 통과/ 같은 경우는 바꿀 필요가 없음
                    
                    # 먼저 두 값을 바꾼다 -> 행과 열을 확인해서 최댓값을 찾는다 -> 다시 자리를 원위치 시킨다
                    board[ny][nx], board[y][x] = board[y][x], board[ny][nx]
                    max_value = max(max_value, find_max())
                    board[ny][nx], board[y][x] = board[y][x], board[ny][nx]

print(max_value)

0,0 부터 N-1,N-1까지 돌아가면서 두 조건을 만족하면 스왑한 후에 사용자 정의 함수에 board를 넘겨줘서 값을 구하는 방식이다.

시간 복잡도는 문제 없다. 한칸에서는 최대 4방향을 움직일 수 있다. 칸의 개수는 N*2이므로 "4 N 제곱"이다. 여기서

또한 파이썬이 좋은 이유가 이런 것에서 있는 것 같다.

"a, b = b, a"를 하면 temp없이 두 값을 간단하게 바꿀 수 있다. 파이썬 장점이 큰 것 같다.

인덱스와 문법이 틀려서 몇번 시도를 했다.