[백준/JAVA] 10026번: 적록색약

📖 문제

 

10026번: 적록색약

 

 

 

💡  풀이 방식

• BFS

 

일반인과 적록색약의 경우를 나눠서 BFS를 수행한다.

1) 일반인의 경우, RGB를 3색을 각각 다르게 본다. R구역과 G구역과 B구역으로 나뉜 구역 수를 구하는 BFS를 수행한다.

visited1 = new boolean[N][N];
for(int i = 0 ; i < N ; i++) {
    for(int j = 0 ; j < N ; j++) {
        if(!visited1[i][j]) {
            bfs1(i, j, map[i][j]);
            p1++;
        }
    }
}

private static void bfs1(int x, int y, char c) {
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[] {x, y});

    visited1[x][y] = true;

    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0 ; d < 4 ; d++) {
            int nx = now[0] + dx[d];
            int ny = now[1] + dy[d];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N)  continue;

            if(!visited1[nx][ny] && map[nx][ny] == c) {
                visited1[nx][ny] = true;
                q.add(new int[] {nx, ny});
            }
        }
    }
}

 

 

 

2) 적록색약의 경우, 빨간색과 초록색을 같게 본다. RG구역과 B구역으로 나뉜 구역 수를 구하는 BFS를 수행한다.

visited2 = new boolean[N][N];
for(int i = 0 ; i < N ; i++) {
    for(int j = 0 ; j < N ; j++) {
        if(!visited2[i][j]) {
            bfs2(i, j, map[i][j]);
            p2++;
        }
    }
}

private static void bfs2(int x, int y, char c) {
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[] {x, y});

    visited2[x][y] = true;

    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0 ; d < 4 ; d++) {
            int nx = now[0] + dx[d];
            int ny = now[1] + dy[d];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited2[nx][ny])  continue;

            if(c == 'R' || c == 'G') {	// 빨간색과 초록색을 같은 색으로 처리
                if(map[nx][ny] == 'R' || map[nx][ny] == 'G') {
                    visited2[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
            else {  // 파란색만 따로 처리
                if(map[nx][ny] == c) {
                    visited2[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N;
    static char[][] map;
    static boolean[][] visited1, visited2;
    static int p1, p2;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        map = new char[N][N];
        for(int i = 0 ; i < N ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = ch[j];
            }
        }
        
        visited1 = new boolean[N][N];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited1[i][j]) {
                    bfs1(i, j, map[i][j]);
                    p1++;
                }
            }
        }
        
        // 적록색약 : R = G
        visited2 = new boolean[N][N];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited2[i][j]) {
                    bfs2(i, j, map[i][j]);
                    p2++;
                }
            }
        }        
        
        System.out.println(p1 + " " + p2);
    }
    
    // 일반인의 구역 구하기
    private static void bfs1(int x, int y, char c) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        visited1[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N)  continue;
                
                if(!visited1[nx][ny] && map[nx][ny] == c) {
                    visited1[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
        }
    }
    
    // 적록색약인의 구역 구하기
    private static void bfs2(int x, int y, char c) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        visited2[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited2[nx][ny])  continue;
                
                if(c == 'R' || c == 'G') {    // R=G
                    if(map[nx][ny] == 'R' || map[nx][ny] == 'G') {
                        visited2[nx][ny] = true;
                        q.add(new int[] {nx, ny});
                    }
                }
                else {  // B
                    if(map[nx][ny] == c) {
                        visited2[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}
 

 

 

 

➕ 다른 풀이 방식

BFS를 2개 따로 만들어 수행하지 않고, 적록색약인 경우 애초에 R과 G를 격자 내에서 같게 처리한 후, BFS 함수는 하나만 만들어 사용하게 하셨다. 이게 분명 더 효율적일 듯✅

백준 10026 - 적록색약 (JAVA 자바)

[백준] 10026번 : 적록색약(JAVA)

 

---

 

 

1회독	2회독	3회독	4회독	5회독
V

---