[백준/java] 10026번: 적록색약 - DFS

10026번: 적록색약

728x90

골드 5티어 치고 어렵지 않았던 문제이다.

 

탐색하고자 하는 범위가 제대로 된 범위인지, 그리고 기존에 방문했었는지를 조사하면 되는데,

 

여기에 추가적으로 초록색과 빨간색이 구분이 가는지에 따라 조건을 다르게 해주면 된다.

 

반응형

 

초록색과 빨간색이 구분이 간다면, 탐색하는 영역의 색이 현재와 같은색인지 비교해주면 된다.

 

하지만 초록색과 빨간색이 구분이 가지 않는 경우, 탐색하는 영역의 색이 파란색인지 아닌지만 비교해주면 된다.

 

package dfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class RedGreenDrug {
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static boolean[][] visit;
	static char[][] map;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = temp.charAt(j);
			}
		}
		
		int zone = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(visit[i][j]) continue;
				char ch = map[i][j];
				dfs(i, j, ch, false);
				zone++;
			}
		}
		
		bw.write(zone + " ");
		zone = 0;
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(visit[i][j]) continue;
				char ch = map[i][j];
				dfs(i, j, ch, true);
				zone++;
			}
		}
		
		bw.write(zone + "\n");
		bw.flush();
	}
	
	public static void dfs(int y, int x, char ch, boolean tf) {
		visit[y][x] = true;
		
		for (int dir = 0; dir < 4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			
			if(!isRange(ny, nx)) continue;
			if(visit[ny][nx]) continue;
			if(!tf) {
				if(map[ny][nx] != ch) continue;
			} else {
				if(ch == 'B') {
					if(map[ny][nx] != ch) continue;
				} else {
					if(map[ny][nx] == 'B') continue;
				}
			}
			
			dfs(ny, nx, ch, tf);
		}
	}
	
	public static boolean isRange(int ny, int nx) {
		if(ny < 0 || ny >= N || nx < 0 || nx >= N) return false;
		return true;
	}
}