10026_적록색약

사용 알고리즘: bfs

사용 언어: java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {

	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static char[][] pic; // 입력받을 배열
	static boolean[][] visited; // 방문처리
	static int n; // 그림의 크기
	static int normal, noRG; // 일반인과 적록색약인이 보는 갯수

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		pic = new char[n][n]; // 배열 초기화
		visited = new boolean[n][n]; // 방문처리 초기화

		for (int i = 0; i < n; i++) {
			String color = br.readLine();
			for (int j = 0; j < n; j++) {
				pic[i][j] = color.charAt(j);
			}
		} // 그림 정보 입력 받음

		// 일반인이 보는 색상 돌기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					normal++;
					bfs(i,j);
				}
			}
		} // 일반인이 보는 색상 돌기 끝

		// fill 함수는 1차원에서만 쓸 수 있음
		for(boolean a[]: visited)
			Arrays.fill(a, false);
		//색약인이 보는 그림 (G는 다 R로 바꾸기)
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(pic[i][j] == 'G') pic[i][j] = 'R';
			}
		}
		// 색약인이 보는 색상 돌기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					noRG++;
					bfs(i,j);
				}
			}
		} // 색약인이 보는 색상 돌기 끝
	
		System.out.println(normal+" "+noRG);
	}

	private static void bfs(int i, int j) {
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] {i, j});
		visited[i][j] = true;
		
		while( !(q.isEmpty()) ) {
			int[] cur = q.poll();
			
			for(int d=0; d<4; d++) { //4방향 탐색
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				
				if(nx>=0 && nx<n && ny>=0 && ny<n) { //범위 안에 있으면
					if( !visited[nx][ny] && pic[i][j]==pic[nx][ny]) { //방문 안 했고, 색이 같으면
						visited[nx][ny] = true; //방문 처리 하고
						q.offer(new int[] {nx,ny});
					}
				}
			}
		}//와일 끝
	}


}

 

 

알고리즘 사용 이유:

구역 별로 나누기 문제

중요:

맵을 따로따로 만드는 게 아니라, 하나의 맵을 활용 = 일반인이 보는 구역을 나누고, 그 맵 그대로 활용하여 문제를 풀어서 메모리 사용량 줄일 수 있음

인사이트:
fill은 1차원 배열에서만 사용 가능하기 때문에 , 2차원 배열에서는 for문 팔요