[알고리즘] 적록색약 - Java

1. 문제

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

2. 풀이

단지번호 붙이기 + 적록색약인 경우 'R'과 'G'를 동일한 색으로 판단해주는 함수 추가!

import java.io.*;
import java.util.*;
import java.awt.Point;

public class 적록색약 {

	public static char[][] arr;
	public static boolean[][] visited;
	public static int[][] nd = {{-1,0}, {1,0}, {0,-1}, {0,1}};
	public static int N;
	public static Queue<Point> q;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		arr = new char[N][N];
		for(int i=0; i<N; i++) {
			char[] ch = br.readLine().toCharArray();
			arr[i] = ch;
		}

		int count1 = 0;
		int count2 = 0;
		
		for(int t=0; t<2; t++) {
			visited = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(!visited[i][j]) {
						if(t==0) count1++;
						else count2++;
						
						visited[i][j] = true;
						bfs(i,j,t);
					}
				}
			}
		}
		
		System.out.println(count1 + " " + count2);
	}

	private static void bfs(int i, int j, int t) {
		q = new LinkedList<Point>();
		q.offer(new Point(i,j));
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int d=0; d<4; d++) {
				int nx = p.x + nd[d][0];
				int ny = p.y + nd[d][1];
				
				if(nx >= N || ny >= N || nx < 0 || ny < 0) continue;
				if(!visited[nx][ny] && checkColor(arr[i][j], arr[nx][ny], t)) {
					visited[nx][ny] = true;
					q.offer(new Point(nx, ny));
				}
			}
		}
	}

	private static boolean checkColor(char curColor, char newColor, int T) {
		if(T == 1 && (curColor=='R' || curColor=='G') && (newColor=='R' || newColor=='G')) {
			return true;
		}
		return curColor == newColor;
	}

}

좋은 웹페이지 즐겨찾기