Algorithm/백준 알고리즘
백준_10026 적록색약(자바) / DFS
미스터로즈
2021. 3. 31. 08:41
시간 & 메모리 제한
문제
입력 & 출력
DFS를 이용한 문제풀이
package com.Back;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Back_10026 {
static int N,ans1=0,ans2=0;
static char[][] map;
static boolean[][] visited;
static int []dx= {-1,1,0,0};
static int []dy= {0,0,-1,1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new char[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String s = st.nextToken();
for (int j = 0; j < N; j++) {
map[i][j]=s.charAt(j);
}
}
//색맹이 아닌 경우
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(!visited[i][j]) {
ans1++;
dfs(i,j);
}
}
}
//색맹인 경우
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j]=='G') {
map[i][j]='R';
}
}
}
//출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(!visited[i][j]) {
ans2++;
dfs(i,j);
}
}
}
System.out.println(ans1+" "+ans2);
}
//dfs를 이용한 풀이
private static void dfs(int x, int y) {
visited[x][y]=true;
for (int k = 0; k < 4; k++) {
int xx = x + dx[k];
int yy = y + dy[k];
if(xx<0 || xx>=N || yy<0 || yy>=N)continue;
if(!visited[xx][yy] && map[x][y]==map[xx][yy]) {
dfs(xx,yy);
}
}
}
}