[백준 - 3085] 사탕 게임 - C++, Python

분류: 구현 /

 

문제

문제 링크

문제 설명

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

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

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

입력

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

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

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

출력

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

 

풀이

- C++

#include <iostream>
using namespace std;

int N, ans;
char board[50][50];
void swap(char &a, char&b) {
    char tmp = a; a = b; b = tmp;
}
void checkRow(int row) {
    int cnt = 1;
    for(int i=1; i<N; i++) {
        if(board[row][i] == board[row][i-1]) {
            cnt++;
            if(cnt > ans) ans = cnt;
        } else cnt = 1;
    }
}
void checkCol(int col) {
    int cnt = 1;
    for(int i=1; i<N; i++) {
        if(board[i][col] == board[i-1][col]) {
            cnt++;
            if(cnt > ans) ans = cnt;
        } else cnt = 1;
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i=0; i<N; i++) cin >> board[i];
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(i < N-1) {
                swap(board[i][j], board[i+1][j]);
                checkCol(j);
                checkRow(i);
                checkRow(i+1);
                swap(board[i][j], board[i+1][j]);
            }
            if(j < N-1) {
                swap(board[i][j], board[i][j+1]);
                checkRow(i);
                checkCol(j);
                checkCol(j+1);
                swap(board[i][j], board[i][j+1]);
            }
        }
    }
    cout << ans;
}

 

- Python

import sys
In = sys.stdin.readline
N = int(In())
graph = [list(In().rstrip()) for _ in range(N)]

def checkRow(row):
    result = cnt = 1
    for col in range(1, N):
        cnt = cnt+1 if graph[row][col-1] == graph[row][col] else 1
        result = max(result, cnt)
    return result

def checkCol(col):
    result = cnt = 1
    for row in range(1, N):
        cnt = cnt+1 if graph[row-1][col] == graph[row][col] else 1
        result = max(result, cnt)
    return result

def swap(row1, col1, row2, col2):
    graph[row1][col1], graph[row2][col2] = graph[row2][col2], graph[row1][col1]

ans = 1
for i in range(N):
    ans = max(ans, checkCol(i), checkRow(i))

if(ans < N):
    for i in range(N):
        for j in range(N):
            if i<N-1 and graph[i][j] != graph[i+1][j]:
                swap(i,j, i+1,j)
                ans = max(ans, checkRow(i), checkRow(i+1), checkCol(j))
                swap(i,j, i+1,j)
            if j<N-1 and graph[i][j] != graph[i][j+1]:
                swap(i,j, i,j+1)
                ans = max(ans, checkCol(j), checkCol(j+1), checkRow(i))
                swap(i,j, i,j+1)
print(ans)

제출했지만 틀린문제를 다시 풀어봤다.

2달 전에 풀다가 틀린 부분을 찾지못해 질문을 올리고 넘긴 문제였는데 다시 풀어보니 쉽게 풀렸다.

머리를 비우고 처음 부터 다시 푸니 오답에 매몰되지않고 쉽게 풀린 것 같다.

행을 스왑했을 때 바뀐 열만 체크 한게 틀린 이유였다. 행을 스왑한경우 행도 체크해줘야한다.

2개월 전 올렸던 내 질문 글, 셀프 대답