시간 & 메모리 제한
문제
입력 & 출력
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);
}
}
}
}
- DFS를 이용해서 문제풀이를 진행했습니다.
- STEP1. 입력값을 받아옵니다..
- STEP2. 색맹인 경우 DFS로 영역의 갯수를 확인합니다.
- STEP3. 색맹의 경우 색을 통일해주고 visited를 초기화 해줍니다.
- STEP4. 색맹인 경우 영역의 수를 세워주고, 값을 출력해주면 됩니다.