[SWEA] 4613. 러시아 국기 같은 깃발

문제 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

SW Expert Academy

풀이

* 조합을 사용해서 백트래킹을 하며 모든 경우를 다 해본다. 

* 첫 행과 마지막 행은 흰색 / 빨간색으로 고정된다. 

2행부터 n-1 행까지의 조합을 구한다. 

* 조합을 구할 때 파란색이 반드시 포함되어야 한다. 

* W = 1 

B = 2

R = 3

으로 치환을 했다. 

색을 칠 할 때 이전의 행에 칠해진 색과 숫자가 같거나, 더 큰 숫자만 칠할 수 있다. 

예를 들어, 흰 -> 파 (O) / 파 -> 흰(X) 

파 -> 빨 (O) / 빨 -> 파(X)

 

* 이 특징을 이용해서 모든 경우를 전부 구하지 않고도 정답을 구할 수 있다. 

* chk[] => 이 배열에는 각 행마다 칠해질 색의 수가 지정된다. 

* n-1 행까지 칠해질 색이 정해졌다면 calc() 에서 정해진 색으로 바꾸기 위해 몇 개의 칸을 바꿔야 하는지 계산하여 반환한다.

 

 

#include <iostream> #include <vector> #include <cstring> #define INF 987654321 using namespace std; //SWEA 4613. 러시아 국기 같은 깃발 //https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE int color[51][51]; int n, m; int ans = INF; int chk[51]; int calc() { int ret = INF; for (int i = 1; i < n - 1; i++) { if (chk[i] == 2) { ret = 0; break; } //이 색으로 바꿔야 하낟. } if (!ret) { for (int i = 1; i < n - 1; i++) { int flag = chk[i]; for (int j = 0; j < m; j++) { if (color[i][j] != flag) { ret++; } } } } return ret; } void dfs(int x, int c) { if (x == n - 1) { int res = calc(); ans = min(ans, res); return; } if (!chk[x]) { int prev = chk[x - 1]; for (int j = prev; j <= 3; j++) { chk[x] = j; dfs(x + 1, j); chk[x] = 0; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; ++tc) { cin >> n >> m; memset(color, 0, sizeof(color)); memset(chk, 0, sizeof(chk)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; if (c == 'W') color[i][j] = 1; else if (c == 'B') color[i][j] = 2; else if (c == 'R') color[i][j] = 3; } } //조합으로 구하기 ans = INF; int res = 0; for (int j = 0; j < m; ++j) { if (color[0][j] != 1) { res++; color[0][j] = 1; } if (color[n - 1][j] != 3) { res++; color[n - 1][j] = 3; } } //1행부터 n-2행까지는 흰 -> 파 -> 빨 순서대로 와야 한다. //각각 몇 개의 행을 차지하는 지는 조합으로 구한다. dfs(1, 1); cout << "#" << tc << " " << res + ans << '\n'; } return 0; }