알고리즘/Baekjoon

[ Baekjoon ] #10026 적록색약

개발생각11 2020. 2. 22. 21:04
반응형

[Baekjoon][https://www.acmicpc.net/problem/10026]

 

그래프 문제 > DFS로 풀이

풀이)

 (1) 영역을 배열값에 저장 : map[n][n] 

 (2) DFS 탐색 메소드를 두개 생성 

     - 적록색약 DFS 탐색 : GetColorWeaknessDFS()

     - 그 외 DFS 탐색 : GetDFS

     // 방문 체크 배열도 각각 선언해서 체크한다. ( visit_for_color_weakness[n][n] / visit[n][n])

 (3) current_color 변수를 선언하여 현재 좌표의 색상을 저장하였고,

     해당 값이 다음 진행 방향이랑 같은지 체크해서 DFS 탐색 트리를 적용하였다.

 (4) 적록색약의 경우 아래 코드와 같이 분기 체크하여 다음 탐색 영역이 G,R 인 경우 같은 값으로 보도록 처리.

   

[ 적록색약 적용 DFS 탐색 코드 ]

 

[ Java > Code ]

 

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Scanner;

public class baekjoon_10026 {

	static int n;
	static char[][] map;
	static int[][] visit;
	static int[][] visit_for_color_weakness;
	
	static int[] xx = {-1, 0, 1, 0};
	static int[] yy = {0, 1, 0, -1};
	static char current_color;
	
	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];
		visit_for_color_weakness = new int[n][n];
		visit = new int[n][n];
		
		int weak_color_answer = 0;
		int color_answer = 0;

		for(int i=0;i<n;i++)
		{
			String str = sc.next();
			for(int j=0;j<n;j++)
			{
				map[i][j] = str.charAt(j);
			}
		}
		
		for(int i =0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(visit[i][j] == 0)
				{
					current_color = map[i][j];
					GetDFS(i, j);
					color_answer++;
				}
				
				if(visit_for_color_weakness[i][j] == 0)
				{
					current_color = map[i][j];
					GetColorWeaknessDFS(i, j);
					weak_color_answer++;
				}
			}
		}
		
		System.out.print(color_answer + " " + weak_color_answer);
	}

	// 적록색약 적용 DFS 탐색 (Red == Green)
	public static void GetColorWeaknessDFS(int x, int y)
	{
		visit_for_color_weakness[x][y] = 1;
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(current_color == 'G' || current_color == 'R')
			{
				if(mx >= 0 && mx < n && my >= 0 && my < n && visit_for_color_weakness[mx][my] == 0 && (map[mx][my] == 'G' || map[mx][my] == 'R'))
				{
					GetColorWeaknessDFS(mx, my);
				}
			}
			else
			{
				if(mx >= 0 && mx < n && my >= 0 && my < n && visit_for_color_weakness[mx][my] == 0 && map[mx][my] == 'B')
				{
					GetColorWeaknessDFS(mx, my);
				}
			}			
		}
	}
	
	// 적록색약 아닌 경우 DFS 탐색
	public static void GetDFS(int x, int y)
	{
		visit[x][y] = 1;
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(mx >= 0 && mx < n && my >= 0 && my < n && visit[mx][my] == 0 && map[mx][my] == current_color)
			{
				GetDFS(mx, my);
			}
		}
	}
}
반응형