[BOJ/JAVA] 백준 10026번 적록색약 (DFS, BFS)

 

✔ 문제

난이도 : 골드5 🥇

10026번: 적록색약

 

✔ 문제 풀이

주어진 예제 처럼 첫째 줄에 NxN의 배열에 해당하는 N이 주어지고

각 칸에 R,G,B중 하나를 색칠한 그림이 둘째 줄부터 주어집니다.

이때 각 색들이 차지하는 구역과, 적록색약인 사람이 봤을 때의 구역을 구하는 문제입니다.

적록색약은 R(빨강)과 G(초록)이 잘 구분되지 않기 때문에 같은 구역으로 생각하여 카운트하도록 코드를 짠다면 쉽게 풀 수 있습니다.

 

 

💡 단순하게 R과 G일 경우 조건을 주어 탐색을 진행하려고 했습니다😭

하지만 조건이 길어지고 메소드가 더 필요하게 되어 다른 풀이를 찾아보던 중 그림을 R은 -> G로 또는 G를 -> R로 바꾸어주면 R과 G를 하나의 구역으로 구분할 수 있게 됩니다!

 

🔎 DFS 풀이

모든 배열을 탐색해야하기 때문에 DFS알고리즘이 먼저 떠올랐습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.lang.StringBuilder;

public class Main{
    static boolean[][] visited;
    static char[][] image;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int n, cnt;
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n][n]; // 방문여부 확인을 위한 배열
        image = new char[n][n]; // 사진

		//주어진 사진에 해당하는 색들을 이차원배열에 채워줍니다.
        for( int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j = 0; j<n; j++){
                color[i][j] = line.charAt(j);
            }
        }

		// 일반적인 경우
        cnt = 0;
        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( !visited[i][j] ){
                    dfs(i, j, image[i][j]);
                    cnt++;
                }
            }
        }
        sb.append(cnt).append(" ");
        
        /*
        * 적록색약인 경우
        * image의 색이 R인 부분을 G로 바꿔줌으로써 R과 G영역을 같은 구역으로 인식하게 합니다.
        * 그 후 방문여부와 카운트를 초기화하여 다시 DFS알고리즘을 수행합니다.
        * */
        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( image[i][j] == 'R' ){
                    image[i][j] = 'G';
                }
            }
        }
        visited = new boolean[n][n];
        cnt = 0;
        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( !visited[i][j] ){
                    dfs(i, j, color[i][j]);
                    cnt++;
                }
            }
        }
        sb.append(cnt);
        System.out.println(sb);

	}

    static void dfs(int y, int x, char color){
        visited[y][x] = true;

        for( int i = 0; i<4; i++){
            int ny = dy[i] + y;
            int nx = dx[i] + x;

            if( ny < 0 || nx < 0 || ny >= n || nx >= n ) continue;
            if( !visited[ny][nx] && image[ny][nx] == color ){
                dfs(ny, nx, color[ny][nx]);
            }
        }

    }
}

 

 

🔎 BFS 풀이

모든 배열을 탐색하여 구역의 수를 카운팅 해야하기 때문에 2중 포문을 사용하여 DFS와 같이 방문하지 않은 방에 대해 BFS알고리즘을 수행합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.lang.StringBuilder;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static boolean[][] visited;
    static char[][] image;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int n, cnt;
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n][n];
        image = new char[n][n];

        //그림 세팅
        for(int i = 0; i<n; i++){
            String line = br.readLine();
            for( int j = 0; j<n; j++){
                image[i][j] = line.charAt(j);
            }
        }

		// 일반적인 경우
        cnt = 0;
        for( int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if( !visited[i][j] ){
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        sb.append(cnt).append(" ");
        
        
		// 적록색약인 경우
        for(int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( image[i][j] == 'G'){
                    image[i][j] = 'R';
                }
            }
        }
        visited = new boolean[n][n];
        cnt = 0;
        for( int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if( !visited[i][j] ){
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        sb.append(cnt);
        System.out.println(sb);
	}
    
     static void bfs(int y, int x){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        visited[y][x] = true;

        while (!queue.isEmpty()) {
            int[] curIndex = queue.poll();
            int curY = curIndex[0];
            int curX = curIndex[1];
            for( int i = 0; i<4; i++){
                int ny = dy[i] + curY;
                int nx = dx[i] + curX;

                if( ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                if( !visited[ny][nx] && image[curY][curX] == image[ny][nx]){
                    queue.offer(new int[]{ny, nx});
                    visited[ny][nx] = true;
                }
            }
        }
    }
}