[너비우선탐색] 백준 10026번 적록색약 - JAVA

 

 

 

---

1. 문제 출처

---

 

10026번: 적록색약

 

 

 

 

---

2. 설계

---

[입력 예시]

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

첫 값은 배열의 크기이다.

다음줄부터는 빨강(R) 파랑(B) 녹색(G) 정보가 어떻게 되어있는지를 받는다.

일반인은 정확하게 3가지 색을 구분할 수 있지만, 적록색약인은 빨강, 녹색을 같은 색으로 본다.

 

나는 다음과 같은 루트로 문제를 풀었다.

 

 

1) 영역을 확인했는지 체크하기 위해 visited 배열을 만든다.

 

 

 

2) 메인 함수에서 2중 for문으로 입력예시의 배열을 전체 돌면서, visited가 false인 부분만 BFS 함수로 보낸다.

- BFS함수에는 visited = false인 부분의 행과 열을 보낸다.

 

3) BFS에서는 같은 색깔의 영역을 visited = true로 만든다.

- Color라는 객체를 넣을 큐를 만들어 준다. (링크드리스트) 물론 Color class도 함께 만들어준다. (행/열/무슨색을 가졌는지 저장)

- 메인에서 가져온 행과 열로 Color 객체를 만들어 큐에 넣어준다.

- While문을 큐가 다 떨어질 때까지 돌린다.

- 큐에 저장된  Color 객체 하나를 꺼내 4방 탐색(상/하/좌/우)을 하며 visited = false인 곳을 큐에 넣는다.

(단, 배열 범위를 넘어가면 안되니 체크해줘야하고, 같은 색깔인지도 확인해줘야한다.)

- 큐가 비었다는 뜻은 더 이상 같은 색깔이 나타나지 않는다는 의미이다.

public static void BFS(int row, int col) {
		int[][] direc = {{-1,0},{1,0},{0,-1},{0,1}};//상 하 좌 우
		Queue<Color> q = new LinkedList<>();
		
		//시작점 저장
		q.add(new Color(row, col, map[row][col]));
		visited[row][col]=true;
		
		while(!q.isEmpty()) {
			Color curr = q.poll();//큐에서 첫 값 꺼내기
			
			//4방 조사
			for(int d=0;d<4;d++) {
				int newR = curr.r+direc[d][0];
				int newC = curr.c+direc[d][1];
				
				if(newR<0 || newR>=N || newC<0 || newC>=N) continue;//범위 체크
				if(map[newR][newC]!=curr.color) continue;//같은 색깔인지 확인
				
				//위의 2가지 제약사항을 확인받고 들어왔다면, 방문하지 않았다면 방문 체크 후 큐에 추가
				if(!visited[newR][newC]) {
					visited[newR][newC]=true;
					q.add(new Color(newR, newC, map[newR][newC]));
				}
			}	
		}
	}

 

4) BFS 함수에서 빠져나왔다는 것은 특정 색깔 영역을 하나 확보했다는 뜻이다.

 

 

5) 1~4번 과정을 일반인의 눈으로 본 영역을 구하기 1번, 적록색약의 눈으로 본 영역 구하기 1번 총 2번 진행할 것이다.

 

6) 적록색맹의 눈으로 보는 영역을 구할 때는 새로운 시작을 위해 visited를 초기화해주고, 빨강과 초록을 구분하지 못하니 초록 영역을 빨강으로 모두 바꾸고 1~4번 과정을 진행해주면 된다.

 

 

 

---

3. 전체 코드

---

package 백준10026;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 적록색약 {
	
	static char[][] map;
	static int N;
	static boolean[][] visited;
	
	static class Color{
		int r;
		int c;
		char color;
		public Color(int r, int c, char color) {
			super();
			this.r = r;
			this.c = c;
			this.color = color;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();//배열 크기
		map = new char[N][N];
		for(int i=0;i<N;i++) {
			map[i] = sc.next().toCharArray();
		}
		
		//일반인 영역 조사
		//visited가 안된 영역 BFS 보내기
		visited = new boolean[N][N];
		int 일반area=0;
		
		for(int startR=0;startR<N;startR++) {
			for(int startC=0;startC<N;startC++) {
				if(!visited[startR][startC]) {
					BFS(startR, startC);
					//BFS에서 나왔다면 영역 1이 추가된 것임
					일반area++;
				}
			}
		}
		
		//적록색맹인 영역 조사
		//R G을 같은 색으로 색칠하기
		for(int startR=0;startR<N;startR++) {
			for(int startC=0;startC<N;startC++) {
				if(map[startR][startC]=='G')map[startR][startC]='R';
			}
		}
		//visited 초기화
		visited = new boolean[N][N];
		//visited가 안된 영역 BFS 보내기
		int 색맹area=0;
		for(int startR=0;startR<N;startR++) {
			for(int startC=0;startC<N;startC++) {
				if(!visited[startR][startC]) {
					BFS(startR, startC);
					//BFS에서 나왔다면 영역 1이 추가된 것임
					색맹area++;
				}
			}
		}
		
		//결과출력
		System.out.println(일반area+" "+색맹area);
	}
	
	public static void BFS(int row, int col) {
		int[][] direc = {{-1,0},{1,0},{0,-1},{0,1}};//상 하 좌 우
		Queue<Color> q = new LinkedList<>();
		
		//시작점 저장
		q.add(new Color(row, col, map[row][col]));
		visited[row][col]=true;
		
		while(!q.isEmpty()) {
			Color curr = q.poll();//큐에서 첫 값 꺼내기
			
			//4방 조사
			for(int d=0;d<4;d++) {
				int newR = curr.r+direc[d][0];
				int newC = curr.c+direc[d][1];
				
				if(newR<0 || newR>=N || newC<0 || newC>=N) continue;//범위 체크
				if(map[newR][newC]!=curr.color) continue;//같은 색깔인지 확인
				
				//위의 2가지 제약사항을 확인받고 들어왔다면, 방문하지 않았다면 방문 체크 후 큐에 추가
				if(!visited[newR][newC]) {
					visited[newR][newC]=true;
					q.add(new Color(newR, newC, map[newR][newC]));
				}
			}	
		}
	}
	
	public static void printArr() {
		for(int startR=0;startR<N;startR++) {
			for(int startC=0;startC<N;startC++) {
				System.out.printf(visited[startR][startC]+" ");
			}
			System.out.println();
		}
	}
}

printArr() 함수로 visited 배열을 일반area++, 색맹area++를 추가해줄 때마다 확인하면 어떻게 영역이 확보되는지 한 눈에 볼 수 있을 것이다.

 

 

---

오랜만에 코드 리뷰 끝~