[백준 3085번] 사탕 게임 - 파이썬

 

① 문제 링크

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

3085번: 사탕 게임

---

② 알고리즘 분류

구현, 브루트포스 알고리즘

---

③ ★문제풀이 Point★

1. 인접한 두 칸을 바꾸는 작업 필요

2. 인접한 두 칸을 바꾼 후 상근이가 먹을 수 있는 사탕의 최대 개수(count_candy) 구하고, 전체 사탕의 최대 개수(ans)와 비교하여 최댓값(ans)을 반환

---

④ 풀이

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

전형적인 브루트포스(완전 탐색) 문제이다.

먼저 사탕의 색이 다른 인접한 두 칸을 고르는 것은 파이썬의 swap(변수 바꾸기)을 이용했다.

그다음 count_candy 함수로 각 사탕의 위치마다 상근이가 먹을 수 있는 사탕 최대 개수를 구하였고, 모든 위치에서 상근이가 먹을 수 있는 최대 개수를 ans로 받아 답을 구하였다.

 

Swap이란??

swap(변수 바꾸기): 두 변수의 값을 서로 바꾸는 것을 의미한다.
예를 들어 a = 3, b =5라고 해보자.
a, b = b, a를 이용하면 a는 b의 값, b는 a의 값으로 바뀌어 a = 5, b = 3이 된다.

 

⑤ 코드

다음 코드는 PyPy3로 작성하였습니다.

# 3085번 사탕 게임

# 최대 개수 세기
def count_candy():
    row_cnt, col_cnt, row_max, col_max = 1, 1, -1e9, -1e9
    # 행 계산
    for i in range(n):
        for j in range(n-1):
            # 행 기준 동일한 색상이라면
            if board[i][j] == board[i][j+1]:
                row_cnt += 1
            else:
                row_cnt = 1
            row_max = max(row_cnt, row_max)
        row_cnt = 1
    # 열 계산
    for j in range(n):
        for i in range(n-1):
        	# 열 기준 동일한 색상이라면
            if board[i][j] == board[i+1][j]:
                col_cnt += 1
            else:
                col_cnt = 1
            col_max = max(col_cnt, col_max)
        col_cnt = 1
	# 먹을 수 있는 최대 사탕 개수 구하기
    answer = max(row_max, col_max)
    return answer


ans = 0

n = int(input())
board = [list(input()) for _ in range(n)]
# 상, 하, 좌, 우 방향
steps = [[-1, 0], [1, 0], [0, -1], [0, 1]]

# 하나씩 살펴보며
for i in range(n):
    for j in range(n):
        # 4가지 방향에 대하여
        for k in range(4):
            nx = i + steps[k][0]
            ny = j + steps[k][1]
            # 보드를 벗어나면 건너뛰기
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            # 인접한 두 칸이 다른 색의 사탕이라면
            if board[i][j] != board[nx][ny]:
                board[nx][ny], board[i][j] = board[i][j], board[nx][ny]
                # 이전의 사탕 개수와 비교하며 최댓값 계산
                ans = max(ans, count_candy())
                # 인접한 두 칸 원위치
                board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
# 정답 출력
print(ans)

 

3085 파이썬 채점 결과

---

3085번 사탕 게임