[백준_10026번] 적록색약

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

10026번: 적록색약

[문제]

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

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

 

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

 

 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100), 둘째 줄부터 N개 줄에는 그림이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_10026 {
	public static int n;
	public static char[][] map;
	public static boolean[][] visited;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy= {0,0,-1,1};
	public static int people=0, patient=0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new char[n][n];
		visited=new boolean[n][n];
		
		// 그림 정보 입력받기
		for(int i=0;i<n;i++) {
			String str=sc.next();
			for(int j=0;j<n;j++) {
				map[i][j]=str.charAt(j);
			}
		}
		// 그림을 탐색하며 방문하지 않았다면 dfs 호출
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(visited[i][j]==false) {
					dfs(i,j);
					people++; // 구역의 개수 count
				}
			}
		}
		
		// 적록색약인 경우를 위해 초기화
		visited=new boolean[n][n];
		// 그림의 빨간색 부분을 초록색으로 바꿔준다.
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j]=='R')
					map[i][j]='G';
			}
		}
		// 그림을 탐색하며 방문하지 않았다면 dfs 호출
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(visited[i][j]==false) {
					dfs(i,j);
					patient++; // 구역의 개수 count
				}
			}
		}
		
		System.out.println(people+" "+patient);
	}
	
	public static 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&&ny>=0&&nx<n&&ny<n) {
				if(map[nx][ny]==map[x][y]&&visited[nx][ny]==false) {
					dfs(nx,ny);
				}
			}
		}
	}
}

 

[고찰]

 이번 문제 또한 전형적인 DFS 문제였다. 우선 적록색약이 아닌 사람이 볼 수 있는 구역의 개수를 구해주고, 그림의 빨간색인 부분을 모두 초록색으로 변경하여 적록색약인 사람에게 보이는 그림으로 바꾸어준다. 이렇게 바꾼 그림에서 구역의 개수를 구해주면 끝인 간단한 문제였다.