[백준] 10026번 - 적록색약 (Java)(○)

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

<문제 분석>

1. R / G / B를 별도의 그룹으로 구분해서 탐색한 결과와 R과 G를 동일 그룹으로 묶어서 탐색한 결과를 도출하는 문제이다.

 

 

<문제 풀이>

1. 상하좌우 탐색을 하는 DFS 알고리즘 문제이다.

2. DFS 함수를 2가지 종류로 만들어서 R/G/B를 모두 구분하는 함수와 R-G / B 로 구분하는 함수로 만들어서 순차적으로 호출한다.

 

 

<코드 구현 #1>

 

import java.util.*;

/*
[백준] 10026번 - 적록색약 (Java)
*/

public class Main {
    static int N;
    static char A[][];
    static boolean visited[][];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        A = new char[N][N];
        for (int i=0; i<N; i++) {
            String str = in.next();
            A[i] = str.toCharArray();
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void DFS(int x, int y) {
        visited[x][y] = true;// 방문처리
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<0 || nx>=N || ny<0 || ny>=N) continue; //탐색지역이 맵 범위밖이면 스킵
            if (visited[nx][ny]) continue;// 탐색 지역이 방문지역이면 스킵
            if (A[x][y] != A[nx][ny]) continue;// 탐색지역이 지금 지역과 다른 지역이면 스킵
            DFS(nx, ny);
        }        
    }

    void DFS_RG(int x, int y) {
        visited[x][y] = true;// 방문처리
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<0 || nx>=N || ny<0 || ny>=N) continue; //탐색지역이 맵 범위밖이면 스킵
            if (visited[nx][ny]) continue;// 탐색 지역이 방문지역이면 스킵
            if (A[x][y] == 'R' && A[nx][ny] == 'B') continue;// 출발점이 'R'이면 탐색지가 'B'일때만 스킵
            if (A[x][y] == 'G' && A[nx][ny] == 'B') continue;// 출발점이 'G'이면 탐색지가 'B'일때만 스킵
            if (A[x][y] == 'B' && (A[nx][ny] == 'R' || A[nx][ny] == 'G')) continue;// 출발점이 'B'이면 탐색지가 다르면 스킵
            DFS_RG(nx, ny);
        }        
    }

    int count;
    void Solve() {
        //R/G/B 구분해서 탐색
        visited = new boolean[N][N];
        count = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j]) continue;// 방문했으면 스킵
                DFS(i, j);
                count++;
            }
        }
        System.out.print(count+" ");
        //R-G/B 구분해서 탐색
        visited = new boolean[N][N];
        count = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j]) continue;// 방문했으면 스킵
                DFS_RG(i, j);
                count++;
            }
        }
        System.out.println(count);

    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

---

<코드구현 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

/*
1. FloodFill 알고리즘을 사용해서 R, G, B로 그룹화하고, RG, B로 그룹화한다.
2. 방문배열을 사용하고 전체탐색이 끝나면 초기화하고 다시 사용한다.
3. BFS함수는 2벌을 준비한다. (R-G-B용, RG-B용)
*/

public class Main {
    static int N;
    static boolean visited[][];
    static char map[][];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    class Node {
        int x, y;
        public Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void BFS(int x, int y, char color) {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(x, y));
        visited[x][y] = true;
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 가지치기 시작
                if (nx<0 || nx>=N || ny<0 || ny>=N) continue; //범위체크
                if (visited[nx][ny]) continue; //방문체크
                if (map[nx][ny] != color) continue; //출발점과 탐색점이 다르면 패스
                visited[nx][ny] = true;
                Q.add(new Node(nx, ny));
            }
        }
    }

    void BFS_RG(int x, int y, char color) {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(x, y));
        visited[x][y] = true;
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 가지치기 시작
                if (nx<0 || nx>=N || ny<0 || ny>=N) continue; //범위체크
                if (visited[nx][ny]) continue; //방문체크
                // 출발점이 'R-G'와 'B'를 구분하여 체크
                if (color == 'R' && map[nx][ny] == 'B') continue;
                if (color == 'G' && map[nx][ny] == 'B') continue;
                if (color == 'B' && 
                    (map[nx][ny] == 'R' || map[nx][ny] == 'G')) continue;
                visited[nx][ny] = true;
                Q.add(new Node(nx, ny));
            }
        }
    }

	void Solve() {
        int count = 0;
        visited = new boolean[N][N];
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j]) continue;
                BFS(i, j, map[i][j]);
                count++;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(count).append(" ");

        count = 0;
        visited = new boolean[N][N];
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j]) continue;
                BFS_RG(i, j, map[i][j]);
                count++;
            }
        }
        sb.append(count);
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        map = new char[N][N];
        for (int i=0; i<N; i++) {
            String str = br.readLine();
            for (int j=0; j<N; j++) {
                map[i][j] = str.charAt(j);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}