[백준] 10026 적록 색약 : 골드 5 (java) - bfs & dfs

✔️ 문제 설명

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

 

 

BFS 와 DFS 두 가지 방법으로 풀어보았다. 

✔️ 문제 풀이 (BFS)

이 풀이는 normal_bfs() 함수와 abnormal_bfs() 함수를 분리하여 정상과 적록색약 로직을 나눠서 짰다.

 

[정상과 적록 색약 로직 나누기]

import java.awt.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

import static java.lang.Math.abs;

class Main{
    static int n;
    static char[][] arr;
    static boolean[][] normal_visited ;
    static boolean[][] abnormal_visited;
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1,-1, 0, 0};
    static int nor = 0;
    static int ab = 0;

    static Queue<Point> q1 = new LinkedList<>();
    static Queue<Point> q2 = new LinkedList<>();
    //RGB
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];

        normal_visited = new boolean[n][n];
        abnormal_visited = new boolean[n][n];

        for(int i = 0; i<n; i++){
            String str = br.readLine();
            for(int j = 0; j<n; j++){
                arr[i][j] = str.charAt(j);
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!normal_visited[i][j])
                {
                    q1.add(new Point(i,j));
                    bfs_normal();
                }
                if(!abnormal_visited[i][j]){
                    q2.add(new Point(i,j));
                    bfs_abnormal();
                }
            }
        }
        System.out.println(nor+ " "+ ab);
    }
    public static void bfs_normal(){
        while(!q1.isEmpty()){
            Point current = q1.poll();
            for(int i = 0; i <4; i++){
                int next_i = current.x + dx[i];
                int next_j = current.y + dy[i];

                if(next_i < 0 || next_i >= n || next_j < 0 || next_j >= n)
                    continue;
                if(normal_visited[next_i][next_j])
                    continue;
                if(arr[next_i][next_j] != arr[current.x][current.y])
                    continue;

                q1.add(new Point(next_i, next_j));
                normal_visited[next_i][next_j] = true;
            }
        }
        nor ++;
    }
    public static void bfs_abnormal(){
        while(!q2.isEmpty()) {
            Point current = q2.poll();
            for (int i = 0; i < 4; i++) {
                int next_i = current.x + dx[i];
                int next_j = current.y + dy[i];

                if (next_i < 0 || next_i >= n || next_j < 0 || next_j >= n)
                    continue;
                if (abnormal_visited[next_i][next_j])
                    continue;
                if(arr[current.x][current.y] == 'B' && arr[next_i][next_j] != 'B')
                    continue;
                if(arr[current.x][current.y] == 'R' && arr[next_i][next_j] == 'B')
                    continue;
                if(arr[current.x][current.y] == 'G' && arr[next_i][next_j] == 'B')
                    continue;


                q2.add(new Point(next_i, next_j));
                abnormal_visited[next_i][next_j] = true;
            }
        }
        ab++;
    }

}

 

 

[적록 색약 확인 전 R = G 같게 만들기]

import java.awt.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

import static java.lang.Math.abs;

class Main{
    static int n;
    static char[][] arr;
    static boolean[][] visited ;
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1,-1, 0, 0};
    static int nor = 0;
    static int ab = 0;

    static Queue<Point> q = new LinkedList<>();

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];

        visited = new boolean[n][n];


        for(int i = 0; i<n; i++){
            String str = br.readLine();
            for(int j = 0; j<n; j++){
                arr[i][j] = str.charAt(j);
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j])
                {
                    q.add(new Point(i,j));
                    bfs();
                    nor++;
                }
            }
        }

        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++){
                if(arr[i][j] == 'R'){
                    arr[i][j] = 'G';
                }
                visited[i][j] = false;
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j])
                {
                    q.add(new Point(i,j));
                    bfs();
                    ab++;
                }
            }
        }

        System.out.println(nor+ " "+ ab);
    }
    public static void bfs(){
        while(!q.isEmpty()){
            Point current = q.poll();
            for(int i = 0; i <4; i++){
                int next_i = current.x + dx[i];
                int next_j = current.y + dy[i];

                if(next_i < 0 || next_i >= n || next_j < 0 || next_j >= n)
                    continue;
                if(visited[next_i][next_j])
                    continue;
                if(arr[next_i][next_j] != arr[current.x][current.y])
                    continue;

                q.add(new Point(next_i, next_j));
                visited[next_i][next_j] = true;
            }
        }
    }


}

 

 

---

 

✔️ 문제 풀이 (DFS)

 

import java.awt.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

import static java.lang.Math.abs;

class Main{
    static int n;
    static char[][] arr;
    static boolean[][] visited ;
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1,-1, 0, 0};
    static int nor = 0;
    static int ab = 0;

    static Queue<Point> q = new LinkedList<>();

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];

        visited = new boolean[n][n];


        for(int i = 0; i<n; i++){
            String str = br.readLine();
            for(int j = 0; j<n; j++){
                arr[i][j] = str.charAt(j);
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j])
                {
                    dfs(i,j);
                    nor++;
                }
            }
        }

        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++){
                if(arr[i][j] == 'R'){
                    arr[i][j] = 'G';
                }
                visited[i][j] = false;
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j])
                {
                    dfs(i,j);
                    ab++;
                }
            }
        }

        System.out.println(nor+ " "+ ab);
    }
    public static void dfs(int x, int y){
        visited[x][y] = true;
        char ch = arr[x][y];
        for(int i = 0; i<4; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if(next_x <0 || next_x >= n || next_y < 0 || next_y >= n)
                continue;
            if(visited[next_x][next_y])
                continue;
            if(arr[next_x][next_y] != ch)
                continue;
            dfs(next_x, next_y);
        }
    }
}