💡 문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
💭 접근
이 문제는 사탕의 위치를 바꿔서 연속적으로 나열되어 있는 사탕의 최대값을 구하는 문제로, 전형적인 구현문제이다. 코드를 보면서 구현 순서대로 알아보자. 크게 3가지 부분으로 나눠져있다.
- 입력, 출력
n = int(input())
candy = [list(input()) for _ in range(n)]
ans = 0입력과, 출력을 어떤 방식으로 저장할지 작성한다.
- 사탕 위치 바꾸기
for i in range(n): # 가로 swap
for j in range(n - 1):
if candy[i][j] != candy[i][j + 1]:
candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
count_candy()
candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j] # 원복
for i in range(n - 1): # 세로 swap
for j in range(n):
if candy[i][j] != candy[i + 1][j]:
candy[i][j], candy[i + 1][j] = candy[i + 1][j], candy[i][j]
count_candy()
candy[i][j], candy[i + 1][j] = candy[i + 1][j], candy[i][j] # 원복전체 사탕에 대해 각각의 사탕을 오른쪽 사탕과 바꾸는 코드와, 전체 사탕에 대해 각각의 사탕을 아래쪽 사탕과 바꾸는 코드를 작성한다. 이때 자리를 바꾼 후, 각 행과 열에 대해 연속하는 사탕의 개수를 센뒤, 다시 원복해주는 부분이 필요하다.
- 사탕의 개수 세기
def count_candy():
global ans
for i in range(n): # 가로 count
cnt = 1
for j in range(n - 1):
if candy[i][j] == candy[i][j + 1]:
cnt += 1
else:
cnt = 1
ans = max(ans, cnt)
for j in range(n): # 세로 count
cnt = 1
for i in range(n - 1):
if candy[i][j] == candy[i + 1][j]:
cnt += 1
else:
cnt = 1
ans = max(ans, cnt)사탕의 위치를 바꿀때마다 위의 함수를 호출하여 모든 가로, 세로 방향에 대해 사탕의 개수를 센 뒤, ans를 갱신해준다.
📒 코드
def count_candy():
global ans
for i in range(n):
cnt = 1
for j in range(n - 1):
if candy[i][j] == candy[i][j + 1]:
cnt += 1
else:
cnt = 1
ans = max(ans, cnt)
for j in range(n):
cnt = 1
for i in range(n - 1):
if candy[i][j] == candy[i + 1][j]:
cnt += 1
else:
cnt = 1
ans = max(ans, cnt)
n = int(input())
candy = [list(input()) for _ in range(n)]
ans = 0
for i in range(n): # 가로 swap
for j in range(n - 1):
if candy[i][j] != candy[i][j + 1]:
candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
count_candy()
candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
for i in range(n - 1): # 세로 swap
for j in range(n):
if candy[i][j] != candy[i + 1][j]:
candy[i][j], candy[i + 1][j] = candy[i + 1][j], candy[i][j]
count_candy()
candy[i][j], candy[i + 1][j] = candy[i + 1][j], candy[i][j]
print(ans)💭 후기
어려운 로직이 있는 것이 아니라 차근차근 구현해보면 쉽게 풀릴 문제
a, b = b, a이 문법을 알고 있다면 더욱 쉽게 풀릴 문제.
🔗 문제 출처
https://www.acmicpc.net/problem/3085
