처음 설계를 할때, 명확하고, 이것이 제대로 돌아가는지, 예외는 없는지까지 고려해야 합니다. 이 문제를 푸는 방법으로는 1. 인접한 사탕을 선택하고, swap 하는 함수 2. swap 을 한 후에 가로로, 세로로 연속된 사탕이 몇개 있는지 검사하는 함수 이렇게 2개의 함수로 나누어서 풀이하면 됩니다. |
/* 1908 사탕게임 1. 사탕을 교환하는 함수 -> 하나씩 이동하는데, 일단 가로로 인접한 것 2개를 교환, 하는 i,j 그리고 i,j를 이동하는데 아래랑 교환하는 것 이렇게 짜도록 하겠습니다. 조사가 끝나면 다시 i,j 를 그대로 변경해주도록 하겠습니다. 2. 교환한 맵에서 가로, 세로로 같은 것이 가장 긴 맵 찾으면 됩니다. bfs 가 아니라, for 문으로 풀면 되겠습니다. */ #include <iostream> #include <algorithm> #include <string> using namespace std; #define SIZE 55 // 55 int map[SIZE][SIZE]; int N; string str; int maxVal; int dx[] = { 0,1 }; int dy[] = { 1,0 }; int curC; int conti_cnt; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { cin >> str; for (int j = 0; j < N; j++) { map[i][j] = str[j]; } } } /* 연속적인 것인지 아닌지 어떻게 알 수 있는가? 처음에 Y를 가지고 있습니다. 그리고, 오른쪽으로 이동, 아래로 이동해봅니다. 이것은 동시에 진행하도록 하겠습니다. 일단 변경을 했습니다. 그리고 연속적인 것이 얼마나 긴지 어떻게 찾을 수 있나요? 오른쪽으로 5번, 아래로 다섯번이렇게 검사하면 되겠습니다. 처음부터 다 검사합니다. */ // 일단 맵은 스왑했습니다. void check(int x, int y, int x2, int y2) { swap(map[x][y], map[x2][y2]);
// 세로로 검사하는 것 for (int i = 0; i < N; i++) { conti_cnt = 0; curC = map[i][0]; conti_cnt++; for (int j = 1; j < N; j++) { if (map[i][j] == curC) { conti_cnt++; // 연속되는 숫자 + 1 을 해주고, maxVal = max(maxVal, conti_cnt); } else { curC = map[i][j]; // 다르면 변경합니다. conti_cnt = 1; } } } //가로로 검사하는 것 for (int j = 0; j < N; j++) { conti_cnt = 0; curC = map[0][j]; conti_cnt++; for (int i = 1; i < N; i++) { if (map[i][j] == curC) { conti_cnt++; maxVal = max(maxVal, conti_cnt); } else { curC = map[i][j]; conti_cnt = 1; } } } swap(map[x][y], map[x2][y2]); } void solve() { // 가로에 대해서 swap 하는 부분 for (int i = 0; i < N; i++) { for (int j = 0; j < (N-1); j++) { check(i, j, i, (j+1)); } } // 세로에 대해서 swap 하는 부분 for (int i = 0; i < (N - 1); i++) { for (int j = 0; j < N; j++) { check(i, j, (i+1), j); } } } int main() { problemIn(); solve(); cout << maxVal << endl; return 0; }
|