백준 10026 적록색약

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

10026번: 적록색약

1. map2개 생성 => 하나는일반인용 입력그대로 받음

색맹용은 기존것 복사 and G이면 R로 바꿔주기

2.모든 미방문노드에 대해 bfs 호출

3. bfs

3-1.4방탐색

3-2.범위안 and 미방문이면 

3-3 부모하고같은색이면 -> 큐에추가(트리확장), 방문처리

3-4. 큐가비었다==가능한것 모두 방문완료->구역생성됨.->answer++

bfs

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_10026_유동훈 {

	static int N;
	static char[][] map;
	static char[][] map2;
	static boolean[][] visit;
	static boolean[][] visit2;
	static Queue<int[]> q = new LinkedList<>();
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int answer;
	static int answer2;
	
	static void print()
	{
		for(int i=0;i<N;++i)
		{
			//st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;++j)
			{
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	/**'
	 * 
	 * @param x
	 * @param y
	 * 탐색시작할 좌표
	 */
	static void bfs(int x, int y)
	{
		//초기위치 큐에 넣기
		q.offer(new int[] {x,y});
		
		while(!q.isEmpty())
		{
			int[] node=q.poll();
			
			//4방탐색
			for(int i=0;i<4;++i)
			{
				int nr=node[0]+dr[i];
				int nc=node[1]+dc[i];
				//미방문 조건 까먹지말기!!!
				if(nr>=0 && nr<N && nc>=0 && nc<N && !visit[nr][nc])
				{
					//부모하고 같은색이면 큐에추가(트리확장), 방문처리 
					if(map[node[0]][node[1]]==map[nr][nc])
					{
						q.offer(new int[] {nr,nc});
						visit[nr][nc]=true;
					}
				}
			}
		}
		
		//큐가비었음==가능한모든곳 방문함->구역하나 생성됨.
		answer++;
	}
	
	static void bfs2(int x, int y)
	{
		//초기위치 큐에 넣기
		q.offer(new int[] {x,y});
		
		while(!q.isEmpty())
		{
			int[] node=q.poll();
			
			//4방탐색
			for(int i=0;i<4;++i)
			{
				int nr=node[0]+dr[i];
				int nc=node[1]+dc[i];
				//미방문 조건 까먹지말기!!!
				if(nr>=0 && nr<N && nc>=0 && nc<N && !visit2[nr][nc])
				{
					//부모하고 같은색이면 큐에추가(트리확장), 방문처리 
					if(map2[node[0]][node[1]]==map2[nr][nc])
					{
						q.offer(new int[] {nr,nc});
						visit2[nr][nc]=true;
					}
				}
			}
		}
		
		//큐가비었음==가능한모든곳 방문함->구역하나 생성됨.
		answer2++;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		//st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(br.readLine());
		map=new char[N][N];
		map2=new char[N][N];	//색맹용
		visit=new boolean[N][N];
		visit2=new boolean[N][N];	//색맹용
		
		for(int i=0;i<N;++i)
		{
			String s=br.readLine();
			for(int j=0;j<N;++j)
			{
				map[i][j]=s.charAt(j);
			}
		}
		
		for(int i=0;i<N;++i)
		{
			//String s=br.readLine();
			for(int j=0;j<N;++j)
			{
				map2[i][j]=map[i][j];
				if(map2[i][j]=='G') map2[i][j]='R';
			}
		}
		
		//모든 미방문 노드에 대해 bfs
		for(int i=0;i<N;++i)
		{
			for(int j=0;j<N;++j)
			{
				if(!visit[i][j])
					bfs(i,j);
			}
		}
		
		q.clear();
		//모든 미방문 노드에 대해 bfs2
		for(int i=0;i<N;++i)
		{
			for(int j=0;j<N;++j)
			{
				if(!visit2[i][j])
					bfs2(i,j);
			}
		}
		
		System.out.print(answer+" ");
		System.out.println(answer2);
		//print();
		
		
		
	}
}