[백준BOJ] 10026번 적록색약.java

 

백준 저지에서 적록색약을 자바를 통해 풀어 보았다. 

 

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

10026번: 적록색약

10026번 적록색약.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

10026번 적록색약

문제

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

설명

각 구역을 세는 것은 BFS, DFS 문제에서 쉽고 자주 나오는 유형이다. 모든 점에 대해서 탐색을 수행하며 방문한 위치에 대해 표시해준다. 만약 방문하지 않은 점이라면 해당 점을 포함하는 구역에 있는 모든 점을 표시할 것이고 방문한 점이라면 그냥 넘어간다. 이렇게 방문하지 않은 점을 세주면 그것이 곧 구역의 수이다.

 

단 이 문제의 경우 적록색약일 경우 초록색과 빨간색을 같은 색으로 봐서 초록색과 빨간색이 붙어 있으면 같은 구역으로 간주한다. 이를 위해 만약 초록색이나 빨간색 점으로 시작한다면 "RG", 파란색이라면 "BB"라는 문자열을 생성하여 방문하는 점의 색인 캐릭터 문자가 포함된다면 같은 구역이 되도록했다.

코드

//10026번 적록색약.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 적록색약_10026 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		char[][] board = new char[N][N];
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<N;j++) {
				board[i][j]=line.charAt(j);
			}
		}
		boolean[][] visit = new boolean[N][N];
		int count=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(!visit[i][j]) {
					bfs(i,j,board,visit,N);
					count++;
				}
			}
		}
		System.out.print(count+" ");
		
		visit = new boolean[N][N];
		count=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(!visit[i][j]) {
					bfs2(i,j,board,visit,N);
					count++;
				}
			}
		}
		System.out.print(count);
	}
    static class point{
    	int i;
    	int j;
    	point(int i, int j){
    		this.i=i;
    		this.j=j;
    	}
    }
    public static void bfs(int i,int j, char[][] board, boolean[][] visit, int N) {
    	int[] dI = {0,0,1,-1};
    	int[] dJ = {1,-1,0,0};
    	
    	visit[i][j]=true;
    	char color = board[i][j];
    	Queue<point> q = new LinkedList<point>();
    	q.add(new point(i,j));
    	while(!q.isEmpty()) {
    		point now = q.poll();
    		for(int d=0;d<4;d++) {
    			int nextI = now.i+dI[d];
    			int nextJ = now.j+dJ[d];
    			if(0<=nextI && nextI<N && 0<=nextJ && nextJ<N) {
    				if(!visit[nextI][nextJ]) {
    					if(board[nextI][nextJ]==color) {
    						visit[nextI][nextJ]=true;
    						q.add(new point(nextI, nextJ));
    					}
    				}
    			}
    		}
    	}
    }
    
    public static void bfs2(int i,int j, char[][] board, boolean[][] visit, int N) {
    	int[] dI = {0,0,1,-1};
    	int[] dJ = {1,-1,0,0};
    	
    	visit[i][j]=true;
    	char color = board[i][j];
    	String colors;
    	if(color=='R' || color=='G') {
    		colors ="RG";
    	}
    	else {
    		colors="BB";
    	}
    	Queue<point> q = new LinkedList<point>();
    	q.add(new point(i,j));
    	while(!q.isEmpty()) {
    		point now = q.poll();
    		for(int d=0;d<4;d++) {
    			int nextI = now.i+dI[d];
    			int nextJ = now.j+dJ[d];
    			if(0<=nextI && nextI<N && 0<=nextJ && nextJ<N) {
    				if(!visit[nextI][nextJ]) {
    					if(colors.charAt(0)==board[nextI][nextJ] || colors.charAt(1)==board[nextI][nextJ]) {
    						visit[nextI][nextJ]=true;
    						q.add(new point(nextI, nextJ));
    					}
    				}
    			}
    		}
    	}
    }
}