[파이썬] 3085. 사탕 게임

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

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

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

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1 

5

YCPZY

CYZZP

CCPPP

YCYZC

CPPZZ

예제 출력 1 

4

힌트

4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

 

 

👱‍♀️ 나의 풀이

import sys
input=sys.stdin.readline

N=int(input())      # 보드의 크기
board=[]
answer=0        # 사탕의 최대 개수
for n in range(N) :
    board.append(list(input().rstrip()))
cnt1=0
cnt2=0

def cnt() :
    global cnt1, cnt2
    # 가로 탐색
    for i in range(N) :
        a=1
        for j in range(1, N) :
            if board[i][j] == board[i][j-1] :
                a+=1
            else :
                cnt1=max(cnt1, a)
                a=1
        cnt1=max(cnt1, a)

    # 세로 탐색
    for i in range(N) :
        a=1
        for j in range(1, N) :
            if board[j][i] == board[j-1][i] :
                a+=1
            else :
                cnt2=max(cnt2, a)
                a=1
        cnt2=max(cnt2, a)
    return max(cnt1, cnt2)

def change(x, y, nx, ny) :
    board[x][y], board[nx][ny]=board[nx][ny], board[x][y]
    result=cnt()
    board[x][y], board[nx][ny]=board[nx][ny], board[x][y]
    return result

# 가로
for x in range(N) :
    for y in range(1, N) :
        if board[x][y-1] != board[x][y] :
            answer=max(change(x, y, x, y-1), answer)
    if answer == N :
        break

if answer < N :
    # 세로
    for x in range(N) :
        for y in range(1, N) :
            if board[y-1][x] != board[y][x] :
                answer=max(change(y, x, y-1, x), answer)
        if answer == N :
            break

print(answer)

가로/세로 방향으로 색이 다른 사탕을 찾고 change 메소드 호출

change 메소드는 가로, 세로 방향으로 전체를 탐색했을 때 같은 색이 연속된 사탕의 최대 길이를 반환

내가 처음에 잘못했던 부분이 가로, 세로 전체 연속 체크를 하지 않고, 사탕 교환한 부분만 연속 체크한 것.

answer이 N이랑 같아지면 더이상 탐색할 필요가 없음

 

 

import sys
input=lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(input()) for i in range(n)]
r=0         # 사탕의 최대 개수

# 가로 탐색
def width() :
    global r

    for i in range(n) :
        c=1
        for j in range(1, n) :
            if a[i][j] == a[i][j-1] :
                c+=1
            else :
                if r < c :	# 최대 개수 r을 갱신
                    r=c
                c=1			# 초기화
        if r < c :  # 한 줄이 모두 같은 경우 처리
            r=c

# 세로 탐색
def height() :
    global r

    for i in range(n) :
        c=1
        for j in range(1, n) :
            if a[j][i] == a[j-1][i] :
                c+=1
            else :
                if r < c :
                    r=c
                c=1
        if r < c :
            r=c

# 가로 교환
for i in range(n) :
    for j in range(1, n) :
        if a[i][j] != a[i][j-1] :   # 색깔이 다르면 사탕 교환
            a[i][j], a[i][j-1]=a[i][j-1], a[i][j]   # 사탕 교환
            width()
            height()
            a[i][j], a[i][j-1]=a[i][j-1], a[i][j]   # 교환한 것을 원래대로

# 세로 교환
for i in range(n) :
    for j in range(1, n) :
        if a[j][i] != a[j-1][i] :
            a[j][i], a[j-1][i]=a[j-1][i], a[j][i]   # 사탕 교환
            width()
            height()
            a[j][i], a[j-1][i]=a[j-1][i], a[j][i]   # 교환한 것을 원래대로

print(r)

다른 사람 풀이를 보다가 빠진 부분 발견하고 추가함.

사탕의 색이 다른 인접한 두 칸을 교환하는 조건을 넣었다.

 

 

# 시간초과
import sys
input=sys.stdin.readline

N=int(input())      # 보드의 크기
board=[]
answer=0        # 사탕의 최대 개수
for n in range(N) :
    board.append(list(input().rstrip()))
dx=[0, 0, -1, 1]
dy=[-1, 1, 0, 0]
cnt1=0
cnt2=0

def cnt() :
    global cnt1, cnt2
    # 가로 탐색
    for i in range(N) :
        a=1
        for j in range(1, N) :
            if board[i][j] == board[i][j-1] :
                a+=1
            else :
                cnt1=max(cnt1, a)
                a=1
        cnt1=max(cnt1, a)

    # 세로 탐색
    for i in range(N) :
        a=1
        for j in range(1, N) :
            if board[j][i] == board[j-1][i] :
                a+=1
            else :
                cnt2=max(cnt2, a)
                a=1
        cnt2=max(cnt2, a)
    return max(cnt1, cnt2)

def change(x, y, nx, ny) :
    board[x][y], board[nx][ny]=board[nx][ny], board[x][y]
    result=cnt()
    board[x][y], board[nx][ny]=board[nx][ny], board[x][y]
    return result

for x in range(N) :
    for y in range(N) :
        for i in range(4) :
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < N and 0 <= ny < N :
                if board[nx][ny] != board[x][y] :       # 다른 색깔 사탕
                    answer=max(change(x, y, nx, ny), answer)
    if answer == N :
        break

print(answer)

3중 for문에 cnt 메소드를 호출하면 O(N^2)

그럼 O(N^4)인가??? 상수니까 4는 제외하고

3중 for문 대신에 가로, 세로 각각 분리하는 게 낫다.

 

 

# 실패
import sys
input = sys.stdin.readline

answer = 0
max_cnt = int(input())
board = [list(input().rstrip()) for _ in range(max_cnt)]
trans_board = list(map(list, zip(*board)))     # 2차원 전치 행렬

def change(lst, trans_board, x, y1, y2) :
    lst[x][y1], lst[x][y2] = lst[x][y2], lst[x][y1]
    trans_board[y1][x], trans_board[y2][x] = trans_board[y2][x], trans_board[y1][x]

def check(lst, y1, y2) :
    global answer
    p_count = max(trans_board[y1].count('P'), trans_board[y2].count('P'))
    c_count = max(trans_board[y1].count('C'), trans_board[y2].count('C'))
    z_count = max(trans_board[y1].count('Z'), trans_board[y2].count('Z'))
    y_count = max(trans_board[y1].count('Y'), trans_board[y2].count('Y'))
    answer = max(answer, max([p_count, c_count, z_count, y_count]))


# 사탕을 교환하지 않고도 최대로 먹을 수 있을까
for i in range(max_cnt) :
    if board[i].count('P') == max_cnt or trans_board[i].count('P') == max_cnt:
        answer = max_cnt
        break
    elif board[i].count('C') == max_cnt or trans_board[i].count('C') == max_cnt :
        answer = max_cnt
        break
    elif board[i].count('Z') == max_cnt or trans_board[i].count('Z') == max_cnt :
        answer = max_cnt
        break
    elif board[i].count('Y') == max_cnt or trans_board[i].count('Y') == max_cnt :
        answer = max_cnt
        break
    else :      # 사탕을 교환해야 함
        for j in range(max_cnt) :       # 열
            for y in [j-1, j+1] :     # 좌우
                if 0 <= y < max_cnt :
                    change(board, trans_board, i, j, y)
                    check(board, j, y)
                    # 다시 원상복구
                    board[i][j], board[i][y] = board[i][y], board[i][j]
                    trans_board[j][i], trans_board[y][i] = trans_board[y][i], trans_board[j][i]

print(answer)

trans_board는 board의 전치 행렬이다. 열을 행으로 써서 쉽게 볼 수 있게 했다.

count로 사탕을 교환하지 않아도 최대로 먹을 수 있는지 본다.

change 메소드는 사탕을 바꾼다. if문으로 사탕의 색깔이 다른지를 확인했어야 했는데..

check 메소드는 개수를 센다.

상하를 비교 안 했구나....

 

 

👍 다른 사람 풀이

# https://it-garden.tistory.com/283
import sys
input=lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(input()) for i in range(n)]
r=0		# 사탕의 최대 개수

# 가로 탐색
def width() :
    global r

    for i in range(n) :
        c=1
        for j in range(1, n) :
            if a[i][j] == a[i][j-1] :
                c+=1
            else :
                if r < c :
                    r=c
                c=1
        if r < c :  # 한 줄이 모두 같은 경우 처리
            r=c

# 세로 탐색
def height() :
    global r

    for i in range(n) :
        c=1
        for j in range(1, n) :
            if a[j][i] == a[j-1][i] :
                c+=1
            else :
                if r < c :
                    r=c
                c=1
        if r < c :
            r=c

# 가로
for i in range(n) :
    for j in range(1, n) :
        a[i][j], a[i][j-1]=a[i][j-1], a[i][j]   # 사탕 교환
        width()
        height()
        a[i][j], a[i][j-1]=a[i][j-1], a[i][j]   # 교환한 것을 원래대로

# 세로
for i in range(n) :
    for j in range(1, n) :
        a[j][i], a[j-1][i]=a[j-1][i], a[j][i]   # 사탕 교환
        width()
        height()
        a[j][i], a[j-1][i]=a[j-1][i], a[j][i]   # 교환한 것을 원래대로

print(r)

 

다른 특별한 방법은 없다. 완전 탐색으로 다 탐색.

먼저 가로 방향으로 사탕을 교환하고 가로, 세로로 연속된 최대 사탕 개수를 찾는다.

교환한 사탕을 다시 원래대로 복귀 후 위 과정 반복.

세로 방향으로 교환할 때도 방법이 같다.

 

 

 

문제 출처 👉 백준