백준 3085번 사탕 게임

문제 링크입니다: https://www.acmicpc.net/problem/3085

동서남북을 다 확인해야하는 DFS 알고리즘 문제로 착각해서 조금 헤맸던 문제였습니다.

핵심은 막대사탕처럼 직선으로 되어 있는 사탕만 먹을 수 있다는 것입니다.

알고리즘은 아래와 같습니다.

1. 양 옆을 바꾸고 제일 길게 먹을 수 있는 사탕의 길이를 파악합니다.

i) 가로로 제일 긴 사탕

ii) 세로로 제일 긴 사탕

iii) i)와 ii) 중 긴 사탕의 길이를 선택합니다.

2. 위 아래를 바꾸고 제일 길게 먹을 수 있는 사탕의 길이를 파악합니다.

i) 가로로 제일 긴 사탕

ii) 세로로 제일 긴 사탕

iii) 마찬가지로 i)와 ii) 중 긴 사탕의 길이를 선택합니다.

3. 1과 2에서 구한 길이 중 더 긴 값을 출력합니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 50;

 

int N;

string board[MAX];

 

int numOfCandy()

{

        int result = 1;

        //양 옆

        for (int i = 0; i < N; i++)

        {

                 int temp = 1;

                 for (int j = 1; j < N; j++)

                         if (board[i][j - 1] == board[i][j])

                                 temp++;

                         else

                         {

                                 result = max(result, temp);

                                 temp = 1;

                         }

                 result = max(result, temp);

        }

        //위 아래

        for (int i = 0; i < N; i++)

        {

                 int temp = 1;

                 for (int j = 0; j < N - 1; j++)

                         if (board[j + 1][i] == board[j][i])

                                 temp++;

                         else

                         {

                                 result = max(result, temp);

                                 temp = 1;

                         }

                 result = max(result, temp);

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> board[i];

 

        int result = 0;

        for(int i=0; i<N; i++)

                 for (int j = 0; j < N - 1; j++)

                 {

                         //양 옆 swap

                         swap(board[i][j], board[i][j + 1]);

                         result = max(result, numOfCandy());

                         swap(board[i][j], board[i][j + 1]);

                         //위 아래 swap

                         swap(board[j][i], board[j + 1][i]);

                         result = max(result, numOfCandy());

                         swap(board[j][i], board[j + 1][i]);

                 }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~