알고리즘/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 인 경우 같은 값으로 보도록 처리.
[ 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);
}
}
}
}
반응형