Algorithm-BOJ-10026

13 Mar 2019

Reading time ~2 minutes

현재가 RGB중에 어느 것인지 확인한 뒤에 일반인의 DFS와 적록색약의 DFS를 두 번 돌려주면 된다.

현재 일반과 적록색약의 visited와 now를 따로 지정해줘야 한다.

일반 DFS

현재와 같다면 방문하면 된다.

if(!rgbVisited[nextR][nextC] && map[nextR][nextC] == rgbNow) {
    rgbDfs(nextR, nextC);
}

적록색약 DFS

현재가 B라면 B인 경우를 찾아 방문하고, 현재가 B가 아니라면(R 또는 G) B가 아닐 때 찾아 방문하면 된다.

if(!rgVisited[nextR][nextC]) {
	if(rgNow == 'B' && map[nextR][nextC] == 'B') {
		rgDfs(nextR, nextC);
	}
	if(rgNow != 'B' && map[nextR][nextC] != 'B') {
		rgDfs(nextR, nextC);
	}
}

메인에서 돌려줄 때 방문했는지 안했는지만 확인해서 각각 DFS를 돌려주면 되는데 메인에서 DFS에서 확인하듯이 확인해서 애를 먹었다.. RGBG GBRR … 같은 경우가 있다면 (0,3)에서 now = G이기 때문에 (1,0)에서 방문을 하지 않는 경우가 생겨버린다!

풀이보기

```c++
    #include <iostream>
    
    char map[101][101];
    bool rgVisited[101][101];
    bool rgbVisited[101][101];
    
    int N;
    
    char rgbNow, rgNow;
    int rg=1, rgb=1;
    
    int mR[4] = { -1 , 0, 1, 0 };
    int mC[4] = { 0, 1, 0, -1 };
    
    void rgbDfs(int row, int col) {
        rgbVisited[row][col] = true;
        
        for(int i=0; i<4; i++) {
            int nextR = row + mR[i];
            int nextC = col + mC[i];
            
            if(nextR >= 0 && nextC>=0 && nextR<N && nextC<N) {
                if(!rgbVisited[nextR][nextC] && map[nextR][nextC] == rgbNow) {
                    rgbDfs(nextR, nextC);
                }
            }
        }
    }
    
    void rgDfs(int row, int col) {
        rgVisited[row][col] = true;
        for(int i=0; i<4; i++) {
            int nextR = row + mR[i];
            int nextC = col + mC[i];
            
            if(nextR >= 0 && nextC>=0 && nextR<N && nextC<N) {
                if(!rgVisited[nextR][nextC]) {
                    if(rgNow == 'B' && map[nextR][nextC] == 'B') {
                        rgDfs(nextR, nextC);
                    }
                    if(rgNow != 'B' && map[nextR][nextC] != 'B') {
                        rgDfs(nextR, nextC);
                    }
                }
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
        scanf("%d", &N);
        
        for(int i=0; i<N; i++) {
            scanf("%s", map[i]);
        }
        
        rgbNow = map[0][0];
        rgNow = map[0][0];
        rgbDfs(0, 0);
        rgDfs(0, 0);
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!rgbVisited[i][j]) {
                    rgb++;
                    rgbNow = map[i][j];
                    rgbDfs(i, j);
                }
                if(!rgVisited[i][j]) {
                    rgNow = map[i][j];
                    rg++;
                    rgDfs(i, j);
    
                }
    
            }
        }
        
        printf("%d %d\n", rgb, rg);
        
        
        return 0;
    }
```

c++Algorithm