JArchive 프로그래밍 일기

문제

사탕게임 백준 3085번

리뷰

기분이 엄청 좋다.

맞는데 왜틀리지.. 맞왜틀 중얼거리다가 드디어 채점창에서 "맞았습니다!" 를 봤다.

고생한 이유는 2가지다.

첫 째, 인접한 칸을 교환 후에, 전체 행, 전체 열을 검사하지 않아서 틀렸었다.

BOJ 질문게시판 글을 보다가 쿵 했다.

오른쪽과 교환한 경우, i행, j열, j+1열 이렇게 3 줄만 검사하면 되는줄 알았었다.

하지만 그게 아니었다. 그림그려보니까 다른 행과 열들도 영향을 받았다.

둘 째, 연속한 사탕개수 cnt를 세는데, max_cnt를 갱신하는 지점이 틀렸었다.

모든 행에서 연속한 사탕개수 cnt를 센다.

여기서 이중 for문 안에서 cnt를 잘 세놓긴 했다.

그런데, cnt 가 증가한 순간마다 max_cnt로 갱신해서 기억해줬어만 한다.

그렇지 않으면( 이중 for문이 끝나고 나서 max_cnt로 갱신하는 경우에는 ) , 똑바로 이중 for문 안에서 최대 cnt를 발견해놓고서도 max_cnt가 알 리가 없다.

읽고 도움을 받은 BOJ 질문게시판 글

인접한 칸을 교환하고 나서, 왜 전체 행, 전체 열을 전부 검사해야 하나?

예시 입력, 출력

질문게시판의 질문과 코드에서 나처럼 고민한 분들의 노고가 느껴졌다.

BOJ질문게시판에 글올리시고 답글 달아주시는 분들 모두 감사드린다. 항상 도움 받고 있다 :)

코드

#include <iostream> 
#include <algorithm>
using namespace std;

// 사탕게임 (3085)

int N;
char B[51][51];
int max_num;

void swap(int i, int j, int d_flag){ // d_flag에 따라 아래 또는 오른쪽과 교환  

    char c = B[i][j];

    if(d_flag){ // 아래와 교환  
        B[i][j] = B[i+1][j];
        B[i+1][j] = c; 

    }else { // 오른쪽과 교환  
        B[i][j] = B[i][j+1];
        B[i][j+1] = c; 
    }
}


void check(int i, int j, int d_flag){

    swap(i, j, d_flag); // 교환 

    int cnt = 1;

    // 모든 행의 가로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){

              if(B[x][y] == B[x][y+1]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }


    // 모든 열의 세로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){
              if(B[y][x] == B[y+1][x]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }

    swap(i, j, d_flag); // 제자리 돌려놓기  

} 

int main(void){

    cin >> N;

     for(int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
            cin >> B[i][j];
        }    
    } // 입력받음  

    for(int i = 0; i < N; i++){ // 탐색  

          for(int j = 0; j < N; j++){

             if(j+1 < N){ // 오른쪽과 교환 가능  
                check(i, j, 0);
            }

            if(i+1 < N){ // 아래와 교환 가능 
                check(i, j, 1);
            }
        }    
    } 

    cout << max_num;    

    return 0;    
}