[BOJ/백준] 3085 사탕 게임

● [문제번호 3085] 사탕 게임

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

3085번: 사탕 게임

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

 

● 풀이 과정

: 세세한 부분까지 고려하여 코드를 작성해야한다.

{상, 하, 좌, 우, 그대로} 컨트롤러를 이용했다.

교환 작업 없이 작성해보려다가 점점 코드가 복잡해지는 것 같아서

교환 작업을 이용하여 작성하였다.

 

1. 컨트롤러에 의한 대상이 범위 밖인 경우 예외처리

2. 교환 → 사탕 수 확인 (행, 열 모두 확인) → 원위치로 교환

 

: 사탕의 개수를 셀 때,

해당 행, 열의 마지막 사탕까지 센 값(cnt)이

현재까지 최댓값(sol)과 비교를 해야한다.

(else 문에 sol = cnt 작업을 하면 마지막 사탕까지 세기만 하고 sol과 비교하지 않는다.)

 

● 주의 할 것

: 예외처리 (범위 밖인 경우)

: 마지막 사탕까지 세기 → 비교까지

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 상, 하, 좌, 우, 교환없음(다른 곳 교환)
int controlx[5] = {-1, 1, 0, 0, 0};
int controly[5] = {0, 0, -1, 1, 0};

char bf[51][51];
int N, sol;

// 사탕 위치 바꾸기
void change(int x1, int y1, int x2, int y2)
{
    char temp = bf[x1][y1];
    bf[x1][y1] = bf[x2][y2];
    bf[x2][y2] = temp;
}

// 먹을 수 있는 사탕의 개수 구하기
void check(int x, int y)
{
    // 행 검사
    int cnt = 0;
    
    for(int n = 0; n < N; n++)
    {
        if(bf[x][y] == bf[x][n])
        {
            cnt++;
            if(sol <= cnt)
                sol = cnt;
        }
        else
            cnt = 0;
    }
    
    // 열 검사
    cnt = 0;
    
    for(int n = 0; n < N; n++)
    {
        if(bf[x][y] == bf[n][y])
        {
            cnt++;
            if(sol <= cnt)
                sol = cnt;
        }
        else
            cnt = 0;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 입력
    for(int a = 0; a < N; a++)
        for(int b = 0; b < N; b++)
            cin >> bf[a][b];
    
    for(int a = 0; a < N; a++)
    {
        for(int b = 0; b < N; b++)
        {
            for(int i = 0; i < 5; i++)
            {
                // 범위를 벗어난 경우
                if(a + controlx[i] < 0)
                    continue;
                else if(a + controlx[i] > N - 1)
                    continue;
                else if(b + controly[i] < 0)
                    continue;
                else if(b + controly[i] > N - 1)
                    continue;
                // 범위를 벗어나지 않은 경우
                else
                {
                    // 교환 → 사탕 수 확인 → 원위치로 교환
                    change(a, b, a + controlx[i], b + controly[i]);
                    check(a, b);
                    change(a, b, a + controlx[i], b + controly[i]);
                }
            }
        }
    }
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [500 - 브루트 포스] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2309	일곱 난쟁이	https://pirateturtle.tistory.com/228
2	3085	사탕 게임	https://pirateturtle.tistory.com/229
3	1476	날짜 계산	https://pirateturtle.tistory.com/230
4	1107	리모컨	https://pirateturtle.tistory.com/231
5	14500	테트로미노	https://pirateturtle.tistory.com/232
6	6064	카잉 달력	https://pirateturtle.tistory.com/233
7	1748	수 이어 쓰기 1	https://pirateturtle.tistory.com/234
8	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/235