백준 10026 적록색약 - c++

JangGwon·2022년 7월 19일
알고리즘
0

문제링크 : https://www.acmicpc.net/problem/10026

문제설명

.
전형적인 bfs를 사용하는 문제이다.
나는 BFS함수안에 juckrock이라는 bool변수를 이용해 R,G,B 3가지 각각 따로 따로 구분할건지, R이랑 G는 동급 그외 B 이런식으로 2가지 종류로 취급하도록 할건지 구분하였다.
그래서 적록색약 아닌 사람 시점으로 구역 갯수를 체크할 땐 juckrock = false / 적록색약 인 사람 시점으로 구역 갯수 체크할 땐 juckrock = true로 바꿔가며 체크 한 구역갯수들을 출력하게하였다.

코드

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
    #include <iostream>
    #include <queue>
    #include <vector>
    #include <cstring>
 
    using namespace std;
 
    int dx[4] = { 0,0, 1, -1};
    int dy[4] = { 1,-1,0,0};
    bool used[101][101];
    char map[101][101];
 
    bool juckrock = false;          // 적록색약 사람인지 아닌지 체크하는 변수 
    int n, area, sarea;
 
    void clear()                    // 방문 배열 초기화 함수 
    {
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <=n; j++)
        {
            used[i][j] = false;
        }
    }
    }
    void check_bfs(int x, int y,char c)             // 주변에 같은 색 찾는 bfs()함수                                                            
    {
        queue<pair<int, int> > q;
        q.push(make_pair(x,y));
        while (!q.empty())
        {
            x = q.front().first;
            y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (xx >= 1 && xx <=n && yy >=1 && yy <= n && !used[yy][xx])
                {
                    if (juckrock == false && map[yy][xx] == c)              // 적록색약 아닌 사람시점 
                    {
                        used[yy][xx] = true;
                        q.push(make_pair(xx,yy));
                    }
                    else if (juckrock == true)                              // 적록색약인 사람 시점 
                    {
                        if (c == 'B' && map[yy][xx] == c)
                        {
                            used[yy][xx] = true;
                            q.push(make_pair(xx,yy));
                        }
                        else if (c == 'R' || c == 'G')                  // R = G
                        {
                            if (map[yy][xx] == 'R' || map[yy][xx] == 'G')
                            {
                                used[yy][xx] = true;
                                q.push(make_pair(xx,yy));
                            }
                        }
                    }
                }
            }
 
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
 
        cin >> n;
        for (int i = 1; i <= n; i++)        // 입력 받기
        {
            for (int j = 1; j <= n; j++)
            {
                char in;
                cin >> in;
                map[i][j] = in;
            }
        }
        for (int i = 1; i <= n; i++)        // 적록색약 아닌사람 시점으로 구역 갯수 확인 하기 
        {
            for (int j =1; j <= n; j++)
            {
                if (used[i][j] == false)
                {
                    area++;
                    check_bfs(j,i,map[i][j]);
                }
            }
        }
        cout << area << " ";        // 적록색약 아닌사람 시점 구역 갯수 출력
        juckrock = true;        // 적록색약 시점 on 
        clear();        // 방문 배열 초기화
        for (int i = 1; i <= n; i++)            // 적록색약 인사람 시점 구역 갯수 확인
        {
            for (int j =1; j <= n; j++)
            {
                if (used[i][j] == false)
                {
                    sarea++;
                    check_bfs(j,i,map[i][j]);
                }
            }
        }
        cout << sarea;
        return 0;
    }
cs
profile
JangGwon
이전 포스트

백준 플레티넘 V 달성

다음 포스트

프로그래머스 : 네트워크 - c++

0개의 댓글