[BAEKJOON_10026 - JAVA] 적록색약

문제

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

10026번: 적록색약

 

 

과정

1. 4방탐색을 활용한 완전탐색.
2. 정상인의 구역을 확보한 후, 적록색약이 보는 그림으로 변형. (기존 그림을 다시 사용하지 않기 때문에 값을 변형)
   (주의 :  만약 복사를 한다면 2차원 배열은 clone으로 깊은 복사가 되지 않는다. 직접 만들어서 사용해야한다.)
3. 이후 변수들의 초기화에 신경을 쓰고 다시 똑같은 완전탐색을 실행.

 

 

 

풀이

• 정상인과 적록색약이 보는 구역을 각각 출력하는 어렵지않은 문제.(solved 레벨은 참고만 하자)
• 구역을 구분하는데는 DFS를 활용.(구역을 나누는 부분엔 DFS구현이 개인적으로 편하다. BFS도 가능)

 

 

 

알고리즘 지식

• DFS or BFS

 

 

JAVA코드

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 BJ10026_적록색약 {

	static int N;
	static boolean visited[][];
	static char drawing[][];
	static int dy[] = { -1, 1, 0, 0 }; // 상하좌우
	static int dx[] = { 0, 0, -1, 1 };

	// 범위 검사
	public static boolean isValid(int row, int col) {
		if (row < 0 || row >= N || col < 0 || col >= N) {
			return false;
		}
		return true;
	}

	// 색약인 사람이 보는 그림으로 초기화
	public static void make_cw() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (drawing[i][j] == 'G') {
					drawing[i][j] = 'R';
				}
			}
		}
	}

	private static void dfs(int row, int col, char color) {
		// 기저조건
		if (visited[row][col]) {
			return;
		}
		// 방문 체크
		visited[row][col] = true;

		// 사방 탐색
		for (int k = 0; k < 4; k++) {
			int nextRow = row + dy[k];
			int nextCol = col + dx[k];

			// 방문한적없고 색이 같은 경우
			if (isValid(nextRow, nextCol) && color == drawing[nextRow][nextCol]) {
				dfs(nextRow, nextCol, color);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		// input
		N = Integer.parseInt(br.readLine());
		drawing = new char[N][N];
		visited = new boolean[N][N];
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			drawing[i] = br.readLine().toCharArray();
		}
		// end of input

		// 정상
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) { // 방문한적이 없는 경우
					cnt++;
					dfs(i, j, drawing[i][j]); // 구역 탐색
				}
			}
		}
		sb.append(cnt + " ");

		// 색약
		visited = new boolean[N][N]; // 방문 초기화
		cnt = 0; // 구역 개수 초기화
		make_cw(); // 적록색약이 보는 그림 만들기

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) { // 방문한적이 없는 경우
					cnt++;
					dfs(i, j, drawing[i][j]); // 구역 탐색
				}
			}
		}

		// output
		sb.append(cnt + "\n");
		bw.write(sb + "");
		bw.flush();
		bw.close();
		br.close();
	}

}