✅문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
ㅤ
✅입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
ㅤ
ㅤ
✅ 알고리즘 분류
- 구현
- 브루트포스 알고리즘
💡풀이
구현 문제 특징상 문제에 제시된 대로 따라서 코드를 짜면 끝난다.
내가 짠 전략은
1. 첫줄 인덱스 부터 오른쪽 & 아래쪽 과 비교를 하며 색이 다를 때 교환한다.
2. 교환 했을 때 배열을 check함수에 넣어 열과 행 탐색을 거쳐 같은 색의 사탕이 가장 연속된 줄을 찾고 그 개수를 ans와 비교하며 최대값에 넣는다
3. 모든 점을 탐색한 후 ans값 print
정답 풀이
import sys
input = sys.stdin.readline
N = int(input()) # NxN 행렬
arr = [list(input()) for _ in range(N)] # 사탕 배열
def check(mat):
r_cnt = c_cnt = 1
answer = 0
for i in range(N):
for j in range(N-1):
if mat[i][j] == mat[i][j+1]:
r_cnt += 1
else:
r_cnt = 1
if mat[j][i] == mat[j+1][i]:
c_cnt += 1
else:
c_cnt = 1
answer = max(r_cnt, c_cnt, answer)
r_cnt = c_cnt = 1
return answer
ans = 0
for i in range(N):
for j in range(N):
if j < N-1 and arr[i][j] != arr[i][j+1]:
arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]
tmp = check(arr)
ans = max(tmp, ans)
arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]
if i < N-1 and arr[i][j] != arr[i+1][j]:
arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
tmp = check(arr)
ans = max(tmp, ans)
arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
print(ans)계속 틀렸다고 떠서 결국 구선생님에게 여쭤봤는데 내 풀이에서 특별한 오류를 못 찾았다..
눈 씻고 3시간은 보다가 결국 진 빠져서 하루를 날린..
실버3 때문에 이렇게 힘들어야 하나 싶다 😂😂
- 틀린 부분 찾아서 수정 완료
check 함수 내에 answer값 갱신을 들여쓰기 한 칸 덜했다..
2번 째 for문 내 반복할 때마다 갱신을 해줘야 하는데 for문이 끝날 때마다 해줘서 AAAAAB같은 경우 5가 최댓값으로 들어가야 하는데 마지막 B 때문에 1이 되어 갱신이 안되는 케이스가 있었다.. 이런 시야를 놓치지 말아야겠다..!
📌 배운 점
한 스텝씩 하는 디버깅이 너무 귀찮아서 매번 눈싸움 하며 돌렸는데 지능을 늘리던지 디버깅을 귀찮아하지 말아야 하던지 해야겠다ㅋㅋㅋㅋㅋㅋ
