백준_3085_사탕게임

백준 3085번, 사탕 게임 문제입니다

#구현 #브루트포스

 

---

 

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력

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

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

 

출력

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

문제 해석하기

문제에 안써있어서 처음에는 헷갈렸는데, 사탕을 1번만 교환한다. 사탕을 1번 교환해서, 가로 또는 세로로 사탕이 최대 몇개나 연속해 있는지를 구하면 되는 문제이다. 

해결 방법 생각하기

1. 가장 길게 연속되어 있는 부분을 어떻게 찾을까?

간단하다. 다 해보면 된다. 즉, 브루트포스 문제이다.

가로는 최대 몇 개의 같은 사탕이 연속되어있는지 다 확인해보고, 세로로도 최대 몇 개의 같은 사탕이 연속되어 있는지 다 확인해보면 된다. 최대 몇 개의 사탕이 연속되어 있는지는 사탕을 서로 교환할 때마다 확인해야하기 때문에 함수로 만들어두면 편할 것 같다.

2. 실행시간 쪼금 줄이기

어떻게 시간을 줄일 수 있을까? 살짝 생각해보니, 이미 N개가 연속되어 있으면, 교환해보지 않아도 된다. 가능한 최대 연속 사탕 개수가 N개이기 때문에, 이 경우에는 어차피 같은 색 사탕끼리 교환해서 N개 연속을 유지해야할 것이기 때문이다. N개가 이미 연속이면 계산을 넘기도록 하자.

3. 구현 방식

색이 다른 인접한 두 칸의 사탕을 교환하고, 가장 긴 연속된 부분을 고른다음 사탕을 모두 먹는다는  문제 그대로 구현하면된다.

1. 색이 다른 인접한 두칸을 고른다

2. 두 칸의 사탕을 교환한다

3. 가장 긴 연속된 부분(가로 또는 세로)을 고른 다음, 그 사탕을 모두 먹는다.

 

구현하기

1. 입력받기

실행 속도는 빠르면 좋으니까 입력 속도를 조금이라도 높이기 위해 input()이 아닌 sys.stdin.readline으로 입력을 받았다. 가끔 실행시간 신경써야하는 문제가 있어서 백준으로 문제를 풀 때면 항상 상단에 넣어놓고 시작한다. 사탕 배열은 리스트 컴프리핸션으로 간단하게 입력을 받았다. 파이썬은 정말 별게 다된다. 편하다. 

import sys
input = sys.stdin.readline

N = int(input())
board = [list(input().strip()) for _ in range(N)]

2. 최대 사탕 개수를 리턴해주는 함수

이전에 언급했듯이, 최대 사탕 개수는 사탕을 교환해 볼 때마다 확인할 예정이기 때문에, 가독성도 올리고 쓰기 편하라고 함수로 빼서 구현을 했다.

def checkMax():
    max_cnt = 1
    for i in range(N):
        # 가로 최대 개수 확인하기
        cnt = 1
        for j in range(1, N):
            if board[i][j-1] == board[i][j]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
        
        # 세로 최대 개수 확인하기
        cnt = 1
        for j in range(1, N):
            if board[j-1][i] == board[j][i]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
            
    return max_cnt

3. 파이썬에서 swap(교환)

파이썬은 별게 다된다2. 다른 언어는 임시 변수 선언해가면서 교환했는데, 파이썬은 한줄로 뿅 끝난다. 이렇게 하면 두 원소의 값이 바뀐다.

def swap(i1, j1, i2, j2):
    board[i1][j1], board[i2][j2] = board[i2][j2], board[i1][j1]

4. 사탕 교환하고 체크하기

문제 그대로 구현해주면 된다. 사탕은 1번만 교환하기 때문에, 교환한 후, 가장 길게 연속된 사탕 개수를 계산했으면, 도로 복구를 해준다. 이미 N개가 연속이면 계산할 필요 없다. 

result = 1   # 먹을 수 있는 최대 사탕 수
result = max(result, checkMax())	# N이면 무조건 최대
    
if result < N:
    for i in range(N):  #가로(i행, row)
        for j in range(N):  #세로(j열, col)
            #(가로) 
            # 1.색이 다른 인접한 두 칸을 골라 교환한다
            if j<N-1 and board[i][j] != board[i][j+1]:
                swap(i,j, i,j+1)    #교환
                result = max(result, checkMax())    # 2.가장 긴 연속부분을 고른다
                swap(i,j, i,j+1)    #원래대로
            #(세로) 
            # 1.색이 다른 인접한 두 칸을 골라 교환한다
            if i<N-1 and board[i][j]!=board[i+1][j]:
                swap(i,j, i+1,j)    #교환
                result = max(result, checkMax())    # 2.가장 긴 연속부분을 고른다
                swap(i,j, i+1,j)    #원래대로
print(result)

 

최종 코드

import sys
input = sys.stdin.readline

N = int(input())
board = [list(input().strip()) for _ in range(N)]

# 최대 사탕 개수를 리턴해주는 함수
def checkMax():
    max_cnt = 1
    for i in range(N):
        # 가로 최대 개수 확인하기
        cnt = 1
        for j in range(1, N):
            if board[i][j-1] == board[i][j]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
        
        # 세로 최대 개수 확인하기
        cnt = 1
        for j in range(1, N):
            if board[j-1][i] == board[j][i]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
            
    return max_cnt

def swap(i1, j1, i2, j2):
    board[i1][j1], board[i2][j2] = board[i2][j2], board[i1][j1]

result = 1   # 먹을 수 있는 최대 사탕 수
result = max(result, checkMax())
    
if result < N:
    for i in range(N):  #가로(i행, row)
        for j in range(N):  #세로(j열, col)
            #(가로) 
            # 1.색이 다른 인접한 두 칸을 골라 교환한다
            if j<N-1 and board[i][j] != board[i][j+1]:
                swap(i,j, i,j+1)    #교환
                result = max(result, checkMax())    # 2.가장 긴 연속부분을 고른다
                swap(i,j, i,j+1)    #원래대로
            #(세로) 
            # 1.색이 다른 인접한 두 칸을 골라 교환한다
            if i<N-1 and board[i][j]!=board[i+1][j]:
                swap(i,j, i+1,j)    #교환
                result = max(result, checkMax())    # 2.가장 긴 연속부분을 고른다
                swap(i,j, i+1,j)    #원래대로
print(result)

 

 

---

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

17425번: 약수의 합