Post

백준_10026번_적록색약[C++]

Posted Updated
By Sung Won Moon
7 min read

img-description [문제 바로가기]

문제

단순한 BFS문제였던거 같은데 푸는데 시간이 좀 걸렸다. 처음에 풀었던 방법과 개선한 방법의 코드 2개를 작성해보았다.

좌표 저장

처음 문제를 풀때 board의 탐색을 최대한 피하고 싶었다. board를 탐색할때마다 O(N^2)시간이 발생하기 때문에 좀 더 효율적으로 정보를 저장하는 방법을 생각해보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

...생략

vector<vector<pair<int,int>>>rgb(3);
int main(){
    //Input board info
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>board[i][j];
            if(board[i][j]=='R')
                rgb[0].push_back({i,j});
            if(board[i][j]=='G')
                rgb[1].push_back({i,j});
            if(board[i][j]=='B')
                rgb[2].push_back({i,j});
        }
    }

...생략

입력을 받을 때 색깔별로 좌표를 저장하는 vector를 이용하면 효율적이지 않을까 싶었다.
1) rgb[0] : board 위에서 'R' 값인 좌표
2) rgb[1] : board 위에서 'G' 값인 좌표
3) rgb[2] : board 위에서 'B' 값인 좌표

BFS

그리고 BFS를 진행하면 되는데, BFS의 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

...생략
int N;
char board[MAXSIZE][MAXSIZE];
bool visited[MAXSIZE][MAXSIZE];
int dy[]={-1,1,0,0};
int dx[] = {0,0,1,-1};
vector<vector<pair<int,int>>>rgb(3); //위치 저장
//범위 체크
bool range_check(int y,int x){
    return y>=0 && y<N && x>=0 && x<N;
}

int bfs(int y,int x,char color){
    if(visited[y][x]) //이미 방문했을 경우
        return 0;
    visited[y][x] = true;
    queue<pair<int,int>> q;
    q.push({y,x});
    while(!q.empty()){
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int next_y = cur_y + dy[i];
            int next_x = cur_x + dx[i];
            if(range_check(next_y,next_x) && !visited[next_y][next_x]&&board[next_y][next_x]==color){
                visited[next_y][next_x]=true;
                q.push({next_y,next_x});
            }
        }
    }
    return 1;
}
..생략

전형적인 BFS의 코드이다. 함수 진입시, 해당 좌표가 visit상태라면 바로 0을 리턴해준다. 그렇지 않다면 탐색을 진행한다.

Main Logic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

..생략
 memset(visited, false,sizeof(visited));
    int r=0;
    for(int i=0;i<rgb[0].size();i++)
        r+=bfs(rgb[0][i].first,rgb[0][i].second,'R');

    int g=0;
    for(int i=0;i<rgb[1].size();i++)
        g+=bfs(rgb[1][i].first,rgb[1][i].second,'G');

    int b=0;
    for(int i=0;i<rgb[2].size();i++)
        b+=bfs(rgb[2][i].first,rgb[2][i].second,'B');
    cout<<r+g+b<<" ";
    memset(visited, false,sizeof(visited));
    for(int i=0;i<rgb[1].size();i++)
        board[rgb[1][i].first][rgb[1][i].second] = 'R'; // board에 있는 모든 G를 R로 바꿈

    r = 0;
    for(int i=0;i<rgb[0].size();i++)
        r+=bfs(rgb[0][i].first,rgb[0][i].second,'R');

    //board에 있는 G를 R로 바꾸긴 했지만, rgb[1]에는 있는 G였던 점들의 좌표를 이용
    for(int i=0;i<rgb[1].size();i++){
        r+=bfs(rgb[1][i].first,rgb[1][i].second,'R');
    }

    b=0;
    for(int i=0;i<rgb[2].size();i++)
        b+=bfs(rgb[2][i].first,rgb[2][i].second,'B');
    cout<<r+b;
}

평범한 사람들의 위한 탐색을 진행 후, board의 정보를 한번 갱신하여 적록색약을 가진 사람들의 탐색을 진행한다.
나는 기존의 board안에 있는 초록색점을 빨간색으로 변경했다.(16~17 line)
그러나 나는 board정보 갱신 후 탐색을 진행할 때, rgb[1]의 좌표들을 사용하지 않아 계속 Wrong Answer가 떴다. 그렇다. 기존의 초록색 점들을 빨간색으로 바꿔도, rgb[0](빨간 점들의 좌표)에는 rgb[1](초록색점들의 좌표)를 저장하지 않았기 때문에 논리적인 오류가 발생했던 것이였다. (24~27line)

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <iostream>
#include<cstring>
#include<queue>
#define MAXSIZE 101
using namespace std;
int N;
char board[MAXSIZE][MAXSIZE];
bool visited[MAXSIZE][MAXSIZE];
int dy[]={-1,1,0,0};
int dx[] = {0,0,1,-1};
vector<vector<pair<int,int>>>rgb(3); //위치 저장
//범위 체크
bool range_check(int y,int x){
    return y>=0 && y<N && x>=0 && x<N;
}

int bfs(int y,int x,char color){
    if(visited[y][x]) //이미 방문했을 경우
        return 0;
    visited[y][x] = true;
    queue<pair<int,int>> q;
    q.push({y,x});
    while(!q.empty()){
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int next_y = cur_y + dy[i];
            int next_x = cur_x + dx[i];
            if(range_check(next_y,next_x) && !visited[next_y][next_x]&&board[next_y][next_x]==color){
                visited[next_y][next_x]=true;
                q.push({next_y,next_x});
            }
        }
    }
    return 1;
}

int main(){
    //Input board info
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>board[i][j];
            if(board[i][j]=='R')
                rgb[0].push_back({i,j});
            if(board[i][j]=='G')
                rgb[1].push_back({i,j});
            if(board[i][j]=='B')
                rgb[2].push_back({i,j});
        }
    }
    memset(visited, false,sizeof(visited));
    int r=0;
    for(int i=0;i<rgb[0].size();i++)
        r+=bfs(rgb[0][i].first,rgb[0][i].second,'R');

    int g=0;
    for(int i=0;i<rgb[1].size();i++)
        g+=bfs(rgb[1][i].first,rgb[1][i].second,'G');

    int b=0;
    for(int i=0;i<rgb[2].size();i++)
        b+=bfs(rgb[2][i].first,rgb[2][i].second,'B');
    cout<<r+g+b<<" ";
    memset(visited, false,sizeof(visited));
    for(int i=0;i<rgb[1].size();i++)
        board[rgb[1][i].first][rgb[1][i].second] = 'R'; // board에 있는 모든 G를 R로 바꿈

    r = 0;
    for(int i=0;i<rgb[0].size();i++)
        r+=bfs(rgb[0][i].first,rgb[0][i].second,'R');

    //board에 있는 G를 R로 바꾸긴 했지만, rgb[1]에는 있는 G였던 점들의 좌표를 이용
    for(int i=0;i<rgb[1].size();i++){
        r+=bfs(rgb[1][i].first,rgb[1][i].second,'R');
    }

    b=0;
    for(int i=0;i<rgb[2].size();i++)
        b+=bfs(rgb[2][i].first,rgb[2][i].second,'B');
    cout<<r+b;
}

좀 더 깔끔한 풀이

첫번째 풀이로 통과 후 질문 게시판을 찾다가 rgb vector를 사용하지 않아도 될 것 같아 더 깔끔하게 코드를 재작성 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
#include<cstring>
#include<queue>
#define MAXSIZE 101
using namespace std;
int N;
char board[MAXSIZE][MAXSIZE];
bool visited[MAXSIZE][MAXSIZE];
int dy[]={-1,1,0,0};
int dx[] = {0,0,1,-1};
vector<vector<pair<int,int>>>rgb(3); //위치 저장
//범위 체크
bool range_check(int y,int x){
    return y>=0 && y<N && x>=0 && x<N;
}

int bfs(int y,int x){
    if(visited[y][x]) //이미 방문했을 경우
        return 0;
    visited[y][x] = true;
    queue<pair<int,int>> q;
    q.push({y,x});
    while(!q.empty()){
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        int cur_c = board[cur_y][cur_x]; //current_color
        q.pop();
        for(int i=0;i<4;i++){
            int next_y = cur_y + dy[i];
            int next_x = cur_x + dx[i];
            if(range_check(next_y,next_x) && !visited[next_y][next_x]&&board[next_y][next_x]==cur_c){
                visited[next_y][next_x]=true;
                q.push({next_y,next_x});
            }
        }
    }
    return 1;
}
int main(){
    //Input board info
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>board[i][j];
        }
    }
    
    memset(visited, false,sizeof(visited));
    int normal_count =0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            normal_count+=bfs(i,j);
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]=='G')
                board[i][j] ='R';
        }
    }
    memset(visited, false,sizeof(visited));
    int half_count = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            half_count+=bfs(i,j);
        }
    }
    cout<<normal_count<<" "<<half_count<<"\n";
}

bfs에서 문자를 check하는 logic을 추가했음을 주의하자.

ProblemSolving
cpp boj
This post is licensed under CC BY 4.0 by the author.