✅ DFS ✅ 연결요소

문제

링크

풀이

1. 문제 접근

적록색약인 사람은 빨강색과 초록색을 같은 색으로 본다.
따라서 연결구역을 색깔에 따라 저장해두고
적록색약이 아닌 사람은 RGB를 각각 모두 더해주고
적록색약인 사람은 RG 중 큰 값과 B를 더해주면 된다.

2. 자료구조 or 알고리즘 선택과 그 이유

BFS, DFS 모두 풀이가 가능한 문제이다.
DFS가 편할 것 같으니 DFS로 풀어보자.

3. 문제 해결 로직 (풀이법)

의사코드

string map[101]
bool visited[101][101]
int RGB[3]
dx = {0,1,0,-1}
dy = {1,0,-1,0}

DFS(y, x){
	visited[y][x] == true
    
    for(i : 0~3){
    	ny = y + dy[i]
        nx = x + dx[i]
        
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        
        if(map[y][x] != map[ny][nx]) continue;
        
        if(visited[ny][nx] == false){
        	DFS(ny, nx)
        }
    }
}

main{
	cin >> N
    for(i : 0 ~ N-1){
    	cin >> map[i]
    }
    
    for(i : 0 ~ N-1){
    	for(j : 0 ~ N-1){
            if(visited[i][j] == false){
                if(map[i][j] == 'R') RGB[0] ++
                if(map[i][j] == 'G') RGB[1] ++
                if(map[i][j] == 'B') RGB[2] ++
            	DFS(i,j)
            }
    	}
    }
}

cout << RGB[0] + RGB[1] + RGB[2] << " "

if(RGB[0] >= RGB[1]) cout << RGB[0]
else cout << RGB[1]

4. 시간 복잡도 분석

O(N^2)

5. 문제에서 중요한 부분

그동안 DFS, BFS를 통해 완전탐색을 했던 문제는 해당 좌표로 이동할 수 있는지, 없는지에 따라 DFS 재귀를 돌껀지 말껀지 결정했었다.
하지만 이문제는 같은 색인지 아닌지 판별하여 결정해야하는 문제였다.