백준_10026 적록색약(자바) / DFS

시간 & 메모리 제한

문제

입력 & 출력

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. 색맹인 경우 영역의 수를 세워주고, 값을 출력해주면 됩니다.