백준 12946번 육각 보드 (C++)

문제 링크 : www.acmicpc.net/problem/12946

12946번: 육각 보드

이 문제에서 먼저 유의해야할 점은 다음과 같다. 

 

1. 육각보드다.

주변의 X자를 판별할때 위치값을 잘 선정해야한다. 무턱대고 사각형이나 정사각형으로 생각하다가는 곧 바로 틀려버린다.

 

2. 색칠하는 갯수의 최대값은 3밖에 나올 수 없다.

 

 

위의 그림에서 X로 표시된 구역을 제외하고 나머지 영역에 색을 칠한다고 가정하자.

색을 넣을때  R는 붉은색, B는 푸른색, P는 보라색으로 가정한다면 위와 같이 넣을 수 있다. 이때 나오는 색조합의 최소갯수는 3개이다.

 

문제 풀이는 다음과 같다. 

 

1. int형 배열 color[51][51]을 만든다. 

2. 이때 color배열의 초기값은 -1이다. -1은 아무 색도 없음을 뜻하며, 0은 붉은색, 1은 푸른색을 뜻한다.

3. color배열을 초기화 해준뒤 아래 조건으로 dfs를 실시한다.

    memset(color,-1,sizeof(color));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j]=='X' && color[i][j]==-1) dfs(i,j,0);
        }
    }

이를 통해 아직 방문하지 않았으며 값이 'X'인 위치에 색을 입히는 작업을 진행하게 된다.

 

4. 아래 코드는 dfs코드이다.

void dfs(int y, int x, int c){
    color[y][x] = c; // 1
    ans = max(ans,1); // 2
    for(int i=0; i<6; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(arr[ny][nx]=='X'){
            if(color[ny][nx]==-1){ // 3
                dfs(ny,nx,1-c);
                ans = max(ans,2);
            }
            else if(color[ny][nx]==c){ // 4
                ans = max(ans,3);
                cout << 3 << "\n";
                exit(0);
            }
        }
    }
}

먼저 1번 코드를 통해 처음 방문한 'X'에 붉은색(=0)을 입혀준다.

동시에 2번 코드를 통해 색을 입힌 최소 횟수를 갱신해준다.

 

5. 3번 코드를 봐보자. 해당 코드를 중심으로 6방향 중, 'X'표시임과 동시에 아직 방문하지 않은 좌표(=-1)가 있다면 그 좌표로 dfs를 진행해준다. 1-c를 통해 반복적으로 0,1,0,1의 색을 입히게 될 것이다. 이때 동시에 색을 입힌 최소 횟수를 갱신해주는 것을 잊지말자.

 

6. 4번 코드를 봐보자. 이 코드는 dfs를 통해 이미 방문한 적이 있는 코드를 다시 가리킬때를 의미한다.

주변에 이미 0과 1로 색이 입혀져있을 것이며, 이때는 3번째 색을 사용해 칠하는 방법밖에 없다.

때문에 최대값 3을 갱신해주고 답을 출력한 뒤 코드를 종료하면 된다.

 

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

int n, my[] = {-1,-1,0,1,1,0}, mx[] = {0,1,1,0,-1,-1}, color[51][51], ny, nx, y, x, ans = 0;
char arr[51][51];

void dfs(int y, int x, int c){
    color[y][x] = c; // 1
    ans = max(ans,1); // 2
    for(int i=0; i<6; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(arr[ny][nx]=='X'){
            if(color[ny][nx]==-1){ // 3
                dfs(ny,nx,1-c);
                ans = max(ans,2);
            }
            else if(color[ny][nx]==c){ // 4
                ans = max(ans,3);
                cout << 3 << "\n";
                exit(0);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }
    memset(color,-1,sizeof(color));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j]=='X' && color[i][j]==-1) dfs(i,j,0);
        }
    }
    cout << ans << "\n";
    return 0;
}