728x90
반응형
문제
https://www.acmicpc.net/problem/10026
풀이 방법
나는 DFS를 사용해서 풀었다. 아직 탐색을 안한 곳을 만나면 범위 카운트 변수에 1를 더해주고 DFS를 시작했다.
적록색약이 아닌 사람은 R, G ,B 모두 구별해서 탐색을 해줬고,
적록색약이라면 ch가 R or G일 때는 R or G 이면 탐색을 하도록 구현하였다.
제출 코드
import java.io.*;
public class BJ_10026_적록색약 {
static int[][] move= {{-1,0},{1,0},{0,-1},{0,1}};
static char[][] map ;
static boolean[][] visitedN;
static boolean[][] visitedG;
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map =new char[N][N];
for (int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
}
int cntN = 0, cntG = 0;
visitedN = new boolean[N][N];
visitedG = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(!visitedN[i][j]) {
cntN++;
notDfs(map[i][j], i,j); //적록색약이 아닌 사람이 봤을때의 구역찾기
}
if(!visitedG[i][j]) {
cntG++;
greenDfs(map[i][j], i,j); //적록색약인 사람이 봤을때의 구역찾기
}
}
}
System.out.print(cntN+" "+cntG);
}
private static void notDfs(char ch, int i, int j) {
visitedN[i][j] = true;
for (int k = 0; k < 4; k++) {
int nr = i+move[k][0];
int nc = j+move[k][1];
if(nr >=0 && nr <N && nc>=0 && nc<N) {
if(!visitedN[nr][nc] && map[nr][nc] ==ch) { //현재 char과 동일하면 탐색
notDfs(ch, nr, nc);
}
}
}
}
private static void greenDfs(char ch, int i, int j) {
visitedG[i][j] = true;
for (int k = 0; k < 4; k++) {
int nr = i+move[k][0];
int nc = j+move[k][1];
if(nr >=0 && nr <N && nc>=0 && nc<N) {
if(!visitedG[nr][nc]) {
if(ch =='R' || ch =='G') { //현재 char이 R ,G 이면 R,G 인경우에 탐색
if(map[nr][nc] == 'R' || map[nr][nc]=='G') {
greenDfs(ch, nr, nc);
}
}else {
if( map[nr][nc] ==ch ) {
greenDfs(ch, nr, nc);
}
}
}
}
}
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 15683 감시 (JAVA) (0) | 2022.02.28 |
---|---|
[BJ] 백준 1244 스위치 켜고 끄기 (JAVA) (0) | 2022.02.24 |
[BJ] 백준 2669 직사각형 네 개의 합집합의 면적구하기 (JAVA) (0) | 2022.02.22 |
[BJ] 백준 1759 암호만들기 (JAVA) (0) | 2022.02.22 |
[BJ] 백준 1260 DFS와 BFS (JAVA) (0) | 2022.02.21 |