[백준] 3085 사탕 게임

문제 출처: 백준 온라인 저지

3085번: 사탕 게임

 

문제 설명

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

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

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

캔디크러쉬를 구현하라는 문제였다.

사진같은 게임판이 주어졌을 때, 딱 한번 인접한 칸 끼리 교체할 수 있을 때 같은 문자가 나타나는 열 또는 행이 최대가 되는 방법을 도출하라는 것이다.

 

구현을 바탕으로 한 문제지만 문제 분류도 그렇고 결국은 브루트 포스로 접근해야하는 문제였다.

 

<정답 코드>

def candy_count(x, y):
    global n
    ea_x, ea_y = 1, 1
    cur = candy[x][y]

    for ny in range(y+1, n):
        if candy[x][ny] == cur:
            ea_y += 1
        else:
            break

    for py in range(y-1, -1, -1):
        if candy[x][py] == cur:
            ea_y += 1
        else:
            break

    for nx in range(x+1, n):
        if candy[nx][y] == cur:
            ea_x += 1
        else:
            break

    for px in range(x-1, -1, -1):
        if candy[px][y] == cur:
            ea_x += 1
        else:
            break

    return max(ea_x, ea_y)



n = int(input())
candy = [list(input()) for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = 0

for x in range(n):
    for y in range(n):
        ans = max(ans, candy_count(x,y))
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and candy[x][y] != candy[nx][ny]:
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]
                ans = max(ans, candy_count(x, y))
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]

print(ans)

브루트포스 문제의 특성인건지 아니면 내가 정말 코드를 너무 못짜서 그런건지, 지저분하게 답이 나왔다.

 

접근 방법은 아래와 같다.

 

1. 입력을 2차원 리스트를 통해 게임보드처럼 생성한다.

2. 반복문을 통해 모든 칸을 순회한다.

3. 각 칸을 순회할 때 주변의 사탕 수를 count한다. 

    3-1. count는 candy_count함수를 통해 이루어진다.

    3-2. candy_count함수는 상하좌우를 모두 순회해 사탕의 행, 열 중 더 많은 사탕의 수를 반환한다.

4. 각 칸에서 인접한 모든 칸에 대해 이동할 수 있고, 원래 칸과 다른 사탕일 때만 스왑한다.

5. 스왑한 후에 candy_count를 한번 더 수행한다.

 

candy_count함수의 경우는 투포인터나 재귀를 통해 좀 더 간략하게 구현할 수 있었을 것 같다.

 

 

브루트포스 문제는 보통 각오로 덤빌 수 있는 문제는 아닌 것 같다. 시간 복잡도도 고려해야하고, 구현 자체도 복잡하고, 코드도 길어져서 한번 틀리면 디버깅하는게 힘든 것 같다.