[백준] 10026번 : 적록색약 - 자바(JAVA)

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

문제 풀이 전 설계

board [i][j] 별로 DFS를 진행한다. 이때 visited [i][j]를 두어 방문된 것은 true로 변환한다.
만약 board[x][y]를 방문해서 DFS를 진행하려고 했지만 visited [x][y] = true라면 DFS가 진행되지 않고 다음으로 넘어갑니다.
DFS횟수만큼 count합니다.
처음 값기준으로 4방 탐색을 하며 값이 동일할 때까지 탐색합니다.
만약 적록색약이라면 적색과 녹색을 동일한 색으로 구분합니다.

이때 isValid부분은 변형해도 되지만 'R'과 'G'를 동일한 색상인 'S'로 변형한 뒤 적록색약이 아닌 사람과 똑같이 진행합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 적록색약
// board[i][j] 별로 DFS를 진행한다. 이때 visited[i][j]를 두어 방문된것은 true로 변환한다.
// 만약 board[x][y]를 방문해서 DFS를 진행하려고 했지만 visited[x][y] = true라면 DFS가 진행되지 않고 다음으로
// 넘어갑니다.
// DFS횟수만큼 count합니다.
// 처음 값기준으로 4방탐색을하며 값이 동일할때까지 탐색합니다.
// 만약 적록색약이라면 적색과 녹색을 동일한 색으로 구분합니다.

public class Main_10026_적록색약 {

	static char[][] board;
	static boolean[][] visited;
	static final int DIRECTION = 4;
	static int N;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		board = new char[N][N];
		visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = str.charAt(j);
			}
		}
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j])
					continue;
				DFS(i, j, board[i][j]);
				count++;
			}
		}
		
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(board[i][j] == 'R' || board[i][j] == 'G')
					board[i][j] ='S';
			}
		}
		
		visited = new boolean[N][N];
		
		int redGreenCount = 0;				
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j])
					continue;
				DFS(i, j, board[i][j]);
				redGreenCount++;
			}
		}
		
		System.out.println(count + " " + redGreenCount);


	}

	private static void DFS(int i, int j, char firstValue) {
		visited[i][j] = true;
		for (int k = 0; k < DIRECTION; k++) {
			int tempY = i + dy[k];
			int tempX = j + dx[k];
			if (!isValid(tempY, tempX, firstValue))
				continue;
			visited[tempY][tempX] = true;
			DFS(tempY, tempX, firstValue);
		}
	}

	
	
	private static boolean isValid(int tempY, int tempX, char firstValue) {
		return (tempY >= 0 && tempX >= 0 && tempY < N && tempX < N && !visited[tempY][tempX]
				&& board[tempY][tempX] == firstValue);
	}
	

}