알고리즘 풀이 - 백준 10026(적록색약, 그래프(BFS, DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxN크기의 그리드에 색상이 표시되어 있을 때, 적록색약의 경우와 일반인의 경우에 구분 가능한 색상 구역의 개수를 구하는 문제

 

2. 풀이

 

가장 기초적인 수준의 그래프 탐색 문제이다.

일반인의 경우와 적록색약인 경우에 그리드를 별도로 저장하여 각각 BFS를 수행한 뒤 구역의 개수를 구하는 방식으로 문제를 해결하였다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① BFS로 풀기

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException{
        // 주어진 값 저장
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // 정상 / 적록색약의 경우를 각각 다르게 저장
        char[][] draw = new char[n][n];
        char[][] weakDraw = new char[n][n];
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < n; j++){
                draw[i][j] = s.charAt(j);
                weakDraw[i][j] = s.charAt(j);
                if(weakDraw[i][j] == 'G'){
                    weakDraw[i][j] = 'R';
                }
            }
        }
        
        int ans = bfs(draw);
        int weak_ans = bfs(weakDraw);
        System.out.println(ans + " " + weak_ans);
        br.close();
    }
    
    private static int bfs(char[][] draw){
        int ans = 0;
        Queue<Integer> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        
        // 모든 위치에 대해서 BFS 탐색 수행 시작
        // 탐색이 시작될 때마다 그룹이 늘어나는 것으로 처리하였다.
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                if(visited[i][j]) continue;
                q.offer(i * n + j);
                visited[i][j] = true;
                ans++;
                
                while(!q.isEmpty()){
                    int c = q.poll();
                    int y = c / n;
                    int x = c % n;
            
                    for(int k=0; k < 4; k++){
                        int ny = y + dy[k];
                        int nx = x + dx[k];
                        if(ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
                
                        if(draw[ny][nx] == draw[y][x]){
                            q.offer(ny * n + nx);
                            visited[ny][nx] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

 

② DFS로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static String[] map = new String[100];
    private static boolean[][] visited = new boolean[100][100];
    private static boolean[][] weakVisited = new boolean[100][100];
    private static int size;

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

        for(int i=0; i < size; i++){
            map[i] = br.readLine();
        }

        int partition = 0;
        int weakPartition = 0;
        for(int i=0; i < size; i++){
            for(int j=0; j < size; j++){
                if(!visited[i][j]){
                    if(!weakVisited[i][j]){
                        weakPartition++;
                    }
                    dfs(i, j, map[i].charAt(j));
                    partition++;
                }
            }
        }

        System.out.println(partition + " " + weakPartition);
        br.close();

    }

    private static void dfs(int y, int x, char color){
        // 범위를 벗어난 경우 반환
        if(y < 0 || size <= y || x >= size || x < 0) return;
        
        // 빨강 또는 초록일 때 적록색약 탐색을 수행한다.
        if(color == 'R' || color == 'G'){
            weakDfs(y, x);
        }

        // 이미 방문 완료된 경우 또는 다른 색상이면 반환
        if(visited[y][x] || color != map[y].charAt(x)){
            return;
        }

        // 4방향으로 탐색 수행
        visited[y][x] = true;
        dfs(y+1, x, color);
        dfs(y, x+1, color);
        dfs(y-1, x, color);
        dfs(y, x-1, color);
    }

    private static void weakDfs(int y, int x){
        if(y < 0 || y >= size || x < 0 || x >= size || map[y].charAt(x) == 'B') return;
        if(weakVisited[y][x]) return;

        weakVisited[y][x] = true;
        weakDfs(y+1, x);
        weakDfs(y, x+1);
        weakDfs(y-1, x);
        weakDfs(y, x-1);

    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.