[JAVA / 자바] 백준 10026번 - 적록색약 (골드 5)

 문제 

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

---

 입력 

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

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

---

 출력 

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

---

---

 문제 접근 방법 

문제의 입력으로 R, G, B 세 가지 색이 칠해진 그림이 주어진다. 이때, 적록색약인 사람이 보는 그림의 색 영역 수와 적록색약이 아닌 사람이 보는 그림의 색 영역의 수를 출력하는 문제이다.

 

필자의 경우 입력의 그림을 적록색약이 아닌 사람이 보는 그림으로 저장하고

입력의 그림에서 G가 칠해진 부분을 R로 치환하여  R, B 두 가지 색이 칠해진 그림으로 바꾸어 적록색약인 사람이 보는 그림으로 저장하여, 총 두 개의 그림을 저장해두었다.

 

따라서 이 그림을 너비 우선 탐색(Breath First Search, BFS), 깊이 우선 탐색(Depth First Search, DFS)으로 색 영역의 시작점을 찾아 색 영역의 개수를 두 그림 각각 파악해주었다.

---

 JAVA 코드 풀이 

1. DFS (Recursion VER.)

	import java.io.*;
	public class Main {
	static int n;
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	String board[][] = new String[n][n];
	String bBoard[][] = new String[n][n];
	for(int i=0; i<n; i++) {
	board[i] = br.readLine().split("");
	for(int j=0; j<n; j++)
	if(board[i][j].equals("R"))
	bBoard[i][j] = "G";
	else
	bBoard[i][j] = board[i][j];
	}
	int sector = 0, bSector = 0;
	for(int i=0; i<n; i++)
	for(int j=0; j<n; j++){
	if(!board[i][j].equals("0")) {
	sector++;
	isSector(i, j, board[i][j], board);
	}
	if(!bBoard[i][j].equals("0")) {
	bSector++;
	isSector(i, j, bBoard[i][j], bBoard);
	}
	}
	System.out.println(sector+" "+bSector);
	}
	static void isSector(int i, int j, String color, String board[][]) {
	if(board[i][j].equals(color)) {
	board[i][j] = "0";
	if(n > i+1)
	isSector(i+1, j, color, board);
	if(0 <= i-1)
	isSector(i-1, j, color, board);
	if(n > j+1)
	isSector(i, j+1, color, board);
	if(0 <= j-1)
	isSector(i, j-1, color, board);
	}
	}
	}

view raw 10026_Recursion.java hosted with ❤ by GitHub

2. DFS (Stack VER.)

	import java.util.*;
	import java.io.*;
	public class Main {
	static int n;
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	String board[][] = new String[n][n];
	String bBoard[][] = new String[n][n];
	for(int i=0; i<n; i++) {
	board[i] = br.readLine().split("");
	for(int j=0; j<n; j++)
	if(board[i][j].equals("R"))
	bBoard[i][j] = "G";
	else
	bBoard[i][j] = board[i][j];
	}
	int sector = 0, bSector = 0;
	for(int i=0; i<n; i++)
	for(int j=0; j<n; j++){
	if(!board[i][j].equals("0")) {
	sector++;
	stack.add(new Spot(i, j));
	dfs(board[i][j], board);
	}
	if(!bBoard[i][j].equals("0")) {
	bSector++;
	stack.add(new Spot(i, j));
	dfs(bBoard[i][j], bBoard);
	}
	}
	System.out.println(sector+" "+bSector);
	}
	static class Spot {
	int r;
	int c;
	Spot(int row, int col) {
	this.r = row;
	this.c = col;
	}
	}
	static Stack<Spot> stack = new Stack<>();
	static void dfs(String color, String board[][]) {
	Spot s;
	while(!stack.isEmpty()) {
	s = stack.pop();
	if(n > s.r+1 && board[s.r+1][s.c].equals(color)) {
	stack.add(new Spot(s.r+1, s.c));
	board[s.r+1][s.c] = "0";
	}
	if(0 <= s.r-1 && board[s.r-1][s.c].equals(color)) {
	stack.add(new Spot(s.r-1, s.c));
	board[s.r-1][s.c] = "0";
	}
	if(n > s.c+1 && board[s.r][s.c+1].equals(color)) {
	stack.add(new Spot(s.r, s.c+1));
	board[s.r][s.c+1] = "0";
	}
	if(0 <= s.c-1 && board[s.r][s.c-1].equals(color)) {
	stack.add(new Spot(s.r, s.c-1));
	board[s.r][s.c-1] = "0";
	}
	}
	}
	}

view raw 10026_Stack.java hosted with ❤ by GitHub

3. BFS

	import java.util.*;
	import java.io.*;
	public class Main {
	static int n;
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	String board[][] = new String[n][n];
	String bBoard[][] = new String[n][n];
	for(int i=0; i<n; i++) {
	board[i] = br.readLine().split("");
	for(int j=0; j<n; j++)
	if(board[i][j].equals("R"))
	bBoard[i][j] = "G";
	else
	bBoard[i][j] = board[i][j];
	}
	int sector = 0, bSector = 0;
	for(int i=0; i<n; i++)
	for(int j=0; j<n; j++){
	if(!board[i][j].equals("0")) {
	sector++;
	queue.add(new Spot(i, j));
	bfs(board[i][j], board);
	}
	if(!bBoard[i][j].equals("0")) {
	bSector++;
	queue.add(new Spot(i, j));
	bfs(bBoard[i][j], bBoard);
	}
	}
	System.out.println(sector+" "+bSector);
	}
	static class Spot {
	int r;
	int c;
	Spot(int row, int col) {
	this.r = row;
	this.c = col;
	}
	}
	static Queue<Spot> queue = new LinkedList<>();
	static void bfs(String color, String board[][]) {
	Spot s;
	while(!queue.isEmpty()) {
	s = queue.remove();
	if(n > s.r+1 && board[s.r+1][s.c].equals(color)) {
	queue.add(new Spot(s.r+1, s.c));
	board[s.r+1][s.c] = "0";
	}
	if(0 <= s.r-1 && board[s.r-1][s.c].equals(color)) {
	queue.add(new Spot(s.r-1, s.c));
	board[s.r-1][s.c] = "0";
	}
	if(n > s.c+1 && board[s.r][s.c+1].equals(color)) {
	queue.add(new Spot(s.r, s.c+1));
	board[s.r][s.c+1] = "0";
	}
	if(0 <= s.c-1 && board[s.r][s.c-1].equals(color)) {
	queue.add(new Spot(s.r, s.c-1));
	board[s.r][s.c-1] = "0";
	}
	}
	}
	}

view raw 10026.java hosted with ❤ by GitHub

 코드 실행 결과 

1. DFS (Recursion VER.) 코드 실행 결과

2. DFS (Stack VER.) 코드 실행 결과

3. BFS 코드 실행 결과

---

 후기 

평범한 그래프 탐색 문제였다고 생각한다.

---

 문제 원본 

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

10026번: 적록색약

 알고리즘 분류 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색