사탕게임
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
문제 풀이
문제 접근
i 행 j 열에 있는 사탕을 Candy[i][j]라고 하자
Candy[i][j]와 자리를 바꿀 수 있는 사탕은 Candy[i+1][j], Candy[i-1][j], Candy[i][j-1], Candy[i][j+1]가 있다.
인접한 사탕의 자리를 바꾸고 각각의 경우에 대해서 Candy[i][j]로 부터 연속으로 같은 색깔의 사탕이 몇 개가 있는지 가로방향 세로방향으로 센다. 모든 경우에서, 가로방향과 세로방향에서 센 사탕의 개수중 가장 큰 값(Max_Value)을 고른다. 모든 사탕을 탐색하면서 각 사탕에 대해서 얻어진 max_value의 최대값을 다시 한번 구한다.
쉽게 설명하면
예를들어
CPP
PCP
CPC의 사탕 배열이 있다고 하자
1열 1행의 인접한 사탕을 교환했을때 가능한 사탕배열은 다음과 같다
1.
PCP
PCP
CPC2.
PPP
CCP
CPC
1번의 경우에는 1열 1행 사탕으로 부터 가로 세로 연속된 사탕의 개수가 각각, 1개 2개로 최대값 2를 갖는다.
2번의 경우에는 1열 1행 사탕으로 부터 가로 세로 연속된 사탕의 개수가 각각, 3개 1개로 최대값 3을 갖는다.
따라서 1열 1행의 max_value는 3이다.
이제 1열 1행 부터 3열 3행까지 모든 사탕을 돌아다니면서 max_value를 구하고 max_value의 최대값을 구할 수 있다.
문제 해결
import sys
N=int(sys.stdin.readline())
Candy=[0]*N
for i in range(N):
Candy[i]=list(sys.stdin.readline().rstrip())
answer_final=0
N[Int] : 사탕 행렬의 크기
Candy[List]: 입력값을 차례대로 저장, 사탕 색깔 행렬
answer_final[Int]: 같은 색을 가진 연속된 사탕의 개수의 최댓값을 저장
def count_sequence(Candy,i,j):
current_color=Candy[i][j]
#가로 방향 연속된 사탕의 개수
count_1=1
for k in range(j-1,-1,-1): #우측방향 연속된 사탕의 개수
if current_color==Candy[i][k]:
count_1+=1
else:
break
for k in range(j+1,N): #좌측방향 연속된 사탕의 개수
if current_color==Candy[i][k]:
count_1+=1
else:
break
#세로 방향 연속된 사탕의 개수
count_2=1
for k in range(i-1,-1,-1): #위쪽방향 연속된 사탕의 개수
if current_color==Candy[k][j]:
count_2+=1
else:
break
for k in range(i+1,N): #아래쪽방향 연속된 사탕의 개수
if current_color==Candy[k][j]:
count_2+=1
else:
break
return max(count_1,count_2)
count_sequence 함수
-Input
Candy[List]: 사탕 색깔 행렬
i[Int]: 행
j[Int]: 열
-Output
Candy[i][j]로부터 가로 세로로 연속된 사탕의 개수의 최댓값
-Function
주어진 위치에서 시작하는 연속된 같은 종류의 사탕 개수를 반환한다.
def switch_location(Candy,i,j,direction):
if direction=="L": #왼쪽에 인접한 사탕과 자리 교환
mem=Candy[i][j]
Candy[i][j]=Candy[i][j-1]
Candy[i][j-1]=mem
elif direction=="R": #오른쪽에 인접한 사탕과 자리 교환
mem=Candy[i][j]
Candy[i][j]=Candy[i][j+1]
Candy[i][j+1]=mem
elif direction=="U": #위쪽에 인접한 사탕과 자리 교환
mem=Candy[i][j]
Candy[i][j]=Candy[i-1][j]
Candy[i-1][j]=mem
elif direction=="D": #아래쪽에 인접한 사탕과 자리 교환
mem=Candy[i][j]
Candy[i][j]=Candy[i+1][j]
Candy[i+1][j]=memswitch_location 함수
-Input
Candy[List]: 사탕 색깔 행렬
i[Int]: 행
j[Int]: 열
dircection[Str]: 인접한 사탕의 방향
-Output
없음
Candy[List]의 주소를 전달받아 Candy배열의 값을 직접 수정한다.
-Function
지정된 방향으로 사탕을 교환한다.
#모든 사탕 탐색
for i in range(N):
for j in range(N):
if j-1>=0:
answer=0
switch_location(Candy,i,j,"L")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"L")
answer_final=max(answer_final,answer)
if j+1<N:
answer=0
switch_location(Candy,i,j,"R")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"R")
answer_final=max(answer_final,answer)
if i-1>=0:
answer=0
switch_location(Candy,i,j,"U")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"U")
answer_final=max(answer_final,answer)
if i+1<N:
answer=0
switch_location(Candy,i,j,"D")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"D")
answer_final=max(answer_final,answer)
print(answer_final)
-중첩 루프: i와 j를 사용하여 모든 사탕을 순회한다
-교환 시도:
- 왼쪽 교환: 셀 (i, j)의 사탕을 왼쪽 (i, j-1)과 교환한다
- 오른쪽 교환: 셀 (i, j)의 사탕을 오른쪽 (i, j+1)과 교환한다
- 위쪽 교환: 셀 (i, j)의 사탕을 위쪽 (i-1, j)과 교환한다
- 아래쪽 교환: 셀 (i, j)의 사탕을 아래쪽 (i+1, j)과 교환한다
-연속 수열 계산: 교환 후 count_sequence 함수를 사용하여 최대 연속 수열의 길이를 계산한다
-최대 길이 업데이트: answer_final에 현재 최대 연속 수열 길이와 비교하여 큰 값을 저장한다
-원래 상태 복구: 교환 후 원래 상태로 복구하여 다음 교환을 준비한다
-결과 출력: answer_final(최대 길이)를 출력한다.
여기서 j+1<N, j-1>=0, i+1<N, i-1>=0 조건이 있는 이유는 수열의 끝부분에서는 사탕을 교환할 수 없기 때문이다. 예를 들어 셀(2,2)에서는 셀(1,2), (3,2), (2,1), (2,3) 모두와 교환할 수 있지만 셀(1,1)에서는 셀(1,2), (2,1)과만 교환할 수 있다.
제출 코드
import sys
def count_sequence(Candy,i,j):
current_color=Candy[i][j]
count_1=1
for k in range(j-1,-1,-1):
if current_color==Candy[i][k]:
count_1+=1
else:
break
for k in range(j+1,N):
if current_color==Candy[i][k]:
count_1+=1
else:
break
count_2=1
for k in range(i-1,-1,-1):
if current_color==Candy[k][j]:
count_2+=1
else:
break
for k in range(i+1,N):
if current_color==Candy[k][j]:
count_2+=1
else:
break
return max(count_1,count_2)
def switch_location(Candy,i,j,direction):
if direction=="L":
mem=Candy[i][j]
Candy[i][j]=Candy[i][j-1]
Candy[i][j-1]=mem
elif direction=="R":
mem=Candy[i][j]
Candy[i][j]=Candy[i][j+1]
Candy[i][j+1]=mem
elif direction=="U":
mem=Candy[i][j]
Candy[i][j]=Candy[i-1][j]
Candy[i-1][j]=mem
elif direction=="D":
mem=Candy[i][j]
Candy[i][j]=Candy[i+1][j]
Candy[i+1][j]=mem
N=int(sys.stdin.readline())
Candy=[0]*N
for i in range(N):
Candy[i]=list(sys.stdin.readline().rstrip())
answer_final=0
for i in range(N):
for j in range(N):
if j-1>=0:
answer=0
switch_location(Candy,i,j,"L")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"L")
answer_final=max(answer_final,answer)
if j+1<N:
answer=0
switch_location(Candy,i,j,"R")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"R")
answer_final=max(answer_final,answer)
if i-1>=0:
answer=0
switch_location(Candy,i,j,"U")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"U")
answer_final=max(answer_final,answer)
if i+1<N:
answer=0
switch_location(Candy,i,j,"D")
answer+=count_sequence(Candy,i,j)
switch_location(Candy,i,j,"D")
answer_final=max(answer_final,answer)
print(answer_final)
'백준 문제 풀이' 카테고리의 다른 글
| [백준 / 파이썬] 백준 1748번 문제 풀이: 수 이어 쓰기 1 (0) | 2025.01.16 |
|---|---|
| [백준 / 파이썬] 백준 6064번 문제 풀이: 카잉 달력 (0) | 2025.01.15 |
| [백준 / 파이썬] 백준 1107번 문제 풀이: 브루트 포스 (Brute Force) (0) | 2024.09.16 |
| [백준 / 파이썬] 백준 1476번 문제 풀이: 브루트 포스 (Brute Force) (1) | 2024.09.15 |
| [백준 / 파이썬] 백준 2309번 문제 풀이: 브루트 포스 (Brute Force) (3) | 2024.09.10 |