[백준] Cow Beauty Pageant

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

5925번: Cow Beauty Pageant

우선 문제부터 요약하면,

3개의 영역을 1개로 합치기 위해서 놓아야 하는 점들의 갯수의 최솟값을 구하는 문제입니다. 문제를 한번 직접 읽어보는 것을 추천합니다.

<Solution>

처음에는 총 3개의 영역이 나오므로,

................
..aaaa....bbb...
...aaaa....bb...
.aaaa......bbb..
........bbbbb...
..ccc....bbb....

문제의 예시로 보면, 이렇게 먼저 영역을 마킹하고, 각각의 영역에 대해 치즈가 녹는 문제 또는 토마토에 전염병이 퍼지는 문제등과 같이 a영역이 확장되어서 처음으로 b를 만나는 시간, c를 만나는 시간을 찾아주는 형태로 하였습니다.

하지만 이렇게 하면, a - b - c 등과 같이 2개씩 연결이 되는 경우만 찾아집니다. 하지만 이런 경우 외에도

4 4
.X..
X..X
..XX
....

또는

5 5
XX...
.....
...XX
.....
XX...

와 같은 예시들이 있습니다.
5x5 예시에서는

5 5
XX...
.*...
.**XX
.*...
XX...

이렇게 4개를 배정하는 것이 최소입니다.

따라서 이런 경우들을 체킹하기 위해서 '.' 인 지점으로부터 3영역까지의 최소 거리를 구해서 계산을 해주는 형식으로 한 가지 case를 추가하여 문제를 해결하였습니다.

실제 구현은 아래와 같습니다.

#include <iostream>
#include <queue>
#include <cstdlib>
 
using namespace std;
 
char grid[50+6][50+6]; 
int visited[50+6][50+6]; 
 
int R,C;
 
int ans;
 
struct rc{
    int r, c;
};

queue <rc> q[3]; // a b c 로 채우자

struct rc memorize_q[3][56*56];

int memq_size[3];
 
int d_row[] = {0, 0, 1, -1};
int d_col[] = {-1, 1, 0, 0};
 
void getinput(){
    cin >> R >> C;
    for(int i = 1; i<=R; i++){
        cin >> &grid[i][1];
    }
}
 
void print_grid(){
    cout << "###############" << endl;
    for(int i = 1; i<=R; i++){
        for(int j = 1; j<=C; j++){
            cout << grid[i][j];
        }
        cout << endl;
    }
}
 
void fillqueue(int row, int column, int q_index){
 
    if(grid[row][column] != 'X') return;
 
    grid[row][column] = 'a' + q_index;
    q[q_index].push((rc){row,column});
    memorize_q[q_index][memq_size[q_index]++] = (rc){row,column};
 
    for(int i = 0; i<4; i++){
        fillqueue(row+d_row[i], column+ d_col[i], q_index);
    }
    // print_grid();
}
 
int bfs(int area_index){
    char to_meet_char1 = (area_index+1) %3 + 'a';
    char to_meet_char2 = (area_index+2) %3 + 'a';
 
    // 내 문자
    char me = 'a' + area_index;
 
    // visited 초기화
    for(int i = 0; i<56; i++){
        for(int j = 0; j<56; j++){
            visited[i][j] = 0;
        }
    }
 
    // queue에 대해 다른 두 문자 모두 찾을때 까지 bfs
 
    int time = 0;
    int meet1_flag = 0;
    int meet2_flag = 0;
    int meet_cnt1 = 987654321;
    int meet_cnt2 = 987654321;
    while(!q[area_index].empty()){
 
        int cur_size = q[area_index].size();
 
        for(int i = 0; i<cur_size; i++){
            rc cur_rc = q[area_index].front(); q[area_index].pop();
 
            for(int j = 0; j<4; j++){
                int next_r, next_c;
 
                next_r = cur_rc.r + d_row[j];
                next_c = cur_rc.c + d_col[j];
 
                if(visited[next_r][next_c]) continue;
                if(grid[next_r][next_c] == me) continue;
                if(!(1<=next_r && next_r <=R && 1<=next_c && next_c <= C))continue; // oob
 
                // 한개로 두개 동시에
                 
                if(grid[next_r][next_c] == to_meet_char1){
                    meet_cnt1 = min(time, meet_cnt1);
                    meet1_flag = 1;
                }
                if(grid[next_r][next_c] == to_meet_char2){
                    meet_cnt2 = min(time, meet_cnt2);
                    meet2_flag = 1;
                }
                // push 해줘야함
                visited[next_r][next_c] = 1;
                q[area_index].push((rc){next_r, next_c});
 
            }
 
 
        }
        if(meet1_flag && meet2_flag){
 
            return meet_cnt1+meet_cnt2;
        }
        time++;   
    }
    return 0;
}
 
void solution(){
    // build 3 queue
    int num_groups = 0;
    for(int i = 1; i<=R; i++){
        for(int j = 1; j<=C; j++){
            if(grid[i][j] == 'X'){
                fillqueue(i, j, num_groups++);
            }
 
        }
    }
    // print_grid();
 
    // 세 영역 각각 확장해서 다른애들이랑 만나는 최솟값 찾자
    int times = 987654321;
    for(int i = 0; i<3; i++){
        times = min(times, bfs(i));
    }
 
    // 점에서도 찾아보기
    // 각각의 점에서 최단거리 찾아보기
    for(int i = 1; i<=R; i++){
        for(int j = 1; j<=C; j++){
            if(grid[i][j] == '.'){
                // find three distance
                int dist_1, dist_2, dist_3;
                dist_1 = dist_2 = dist_3 = 987654321;
 
                // 1번 영역과 최단거리
                for(int k = 0; k<memq_size[0]; k++){
                    rc tmpcur = memorize_q[0][k];
                    dist_1 = min(dist_1, abs(tmpcur.r - i) + abs(tmpcur.c - j));
                }
 
                // 2번 영역과 최단거리
                for(int k = 0; k<memq_size[1]; k++){
                    rc tmpcur = memorize_q[1][k];
                    dist_2 = min(dist_2, abs(tmpcur.r - i) + abs(tmpcur.c - j));
                }
                // 3번 영역과 최단거리
                for(int k = 0; k<memq_size[2]; k++){
                    rc tmpcur = memorize_q[2][k];
                    dist_3 = min(dist_3, abs(tmpcur.r - i) + abs(tmpcur.c - j));
                }
                // cout << "DEBUG DISTSANCE : " << dist_1 << ' '<< dist_2 << ' ' << dist_3 << endl;
                times = min(times, dist_1+dist_2+dist_3-2);
 
            }
 
        }
    }
    ans = times;
}
int main(){
    getinput();
    // print_grid();
     
    solution();
 
    cout << ans << endl;
 
    return 0;
}

 

<참고>

case 1 : 각 영역간 최단 거리를 구해서 가장 긴것 빼고 게산

case 2 : 특정 점에서 3영역을 연결하는 경우 계산

case 1, 2 중 더 적은 갯수 사용한게 답.

 

이 때, case 1을 나는 bfs를 이용해 계산했는데, 그냥 직접 점과 점사이 거리들 구해서 해도 될듯함.

또한 내부의 점들을 사전에 걸러주면 시간을 줄일 수 있을 듯 함.