[BOJ] 백준 10026번:적록색약

date

Aug 23, 2022

slug

boj-10026

author

status

Public

문제링크

10026번: 적록색약

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

문제 분석 및 설계

주어진 2차원 배열이 몇 개의 구역으로 나뉘어 있는지 판단하는 문제

⇒ 구역 수 = BFS 탐색 횟수

BFS 시행을 위해 Node 클래스 생성

(r, c) 와 color(R/G/B) 저장

BFS 동작

2차원 배열에 대하여 bfs 시행, Queue 이용

While (q.empty()) //새로운 구역에 대한 bfs 시작

While (q.empty()) //연결 노드가 있다면 계속 bfs 시행

현재 Node와 상하좌우로 연결된 4개의 노드에 대하여

갈 수 있다면(범위 index 이내 && 색이 같을 경우)
q.add(연결노드)

더이상 연결된 노드가 없다면(== q.empty())

2차원 배열 노드 중 아직 탐색 안 한 노드를 추가한 후 다시 처음 while 문으로 돌아가서 bfs 시행

조건

적록색약이 아닌 사람이 봤을 때

R ≠ G ≠ B

적록색약인 사람이 봤을 때

R = G
R ≠ G
G ≠ B

고민) 적록색약 조건문을 좀 더 Compact 하게 바꿀 수 없을까?


if((color=='B'&&map[r][c-1]=='B')||(color!='B'&&map[r][c-1]!='B'))

현재 조건문:

현재 색상이 B(파랑)인 경우, 인접 색상도 B여야 하고

현재 색상이 B가 아닌 경우, 인접 색상도 B가 아니어야 함

→ 캐릭터를 계속해서 비교하는 것이 비효율적으로 코드가 길고 안예쁨..

방법 1) 비-적록색약 사람 bfs 탐색할 때 G → B 로 변경

장점: BFS 함수를 굳이 2개 만들지 않고도 1개의 BFS 함수로도 처리 가능

단점: map의 원본 데이터가 변경됨. 알고리즘적으론 큰 문제 없으나 원본 데이터를 훼손시키는 것은 지양하는 게 좋을 것 같음

방법 2) 색깔을 홀수, 짝수로 지정하여 합산 확인

R = 1 (홀수), G = 3 (홀수), B = 2 (짝수)

가능한 경우: 짝수

R + R = 짝수
G + G = 짝수
R + G = 짝수
B + B = 짝수

그외: 홀수

R + B = 홀수
G + B = 홀수

적록색약이 아닌 사람일 경우: 숫자가 같은지 확인

적록색약인 사람일 경우: 숫자의 합이 짝수인지 홀수인지 확인

코드


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

class Node {
	int r, c;
	char color;
	
	public Node(int r, int c, char color) {
		this.r = r;
		this.c = c;
		this.color = color;
	}
}

public class Main_BOJ_10026_적록색약_G5 {
	public static int N;
	public static char[][] map;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		System.out.print(bfs1());
		System.out.print(" ");
		System.out.print(bfs2());
	}//main
	
	public static int bfs1() {
		int division = 0;
		boolean[][] visited = new boolean[N][N];
		Queue<Node> q = new LinkedList<>();
		
		q.add(new Node(0,0, map[0][0]));
		visited[0][0] = true;
		
		while(!q.isEmpty()) {
			//현재 구역 탐색
			division++;
			while(!q.isEmpty()) {
				//갈 수 있을 때까지 가면서 visited[][] = true; 변경
				Node current = q.poll();
				int r = current.r;
				int c = current.c;
				char color = current.color;
//				System.out.println("poll: ("+r+", "+c+"), "+color+"!!");
				//상하좌우, 범위 내이고, 안갔고, 색이 같으면 진행
				if(r-1 >= 0 && map[r-1][c] == color && !visited[r-1][c]) {
					q.add(new Node(r-1, c, color));
					visited[r-1][c] = true;
				}
				if(r+1 < N && map[r+1][c] == color && !visited[r+1][c]) {
					q.add(new Node(r+1, c, color));
					visited[r+1][c] = true;
				}
				if(c-1 >= 0 && map[r][c-1] == color && !visited[r][c-1]) {
					q.add(new Node(r, c-1, color));
					visited[r][c-1] = true;
				}
				if(c+1 < N && map[r][c+1] == color && !visited[r][c+1]) {
					q.add(new Node(r, c+1, color));
					visited[r][c+1] = true;
				}
			}//현재구역 탐색 while
			
			//아직 탐색 안한 노드 추가
			search:
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						q.add(new Node(i, j, map[i][j]));
						visited[i][j] = true;
						break search;
					}
				}
			}
		}
		
		return division;
	}
	
	//적록색
	public static int bfs2() {
		int division = 0;
		boolean[][] visited = new boolean[N][N];
		Queue<Node> q = new LinkedList<>();
		
		q.add(new Node(0,0, map[0][0]));
		visited[0][0] = true;
		
		while(!q.isEmpty()) {
			//현재 구역 탐색
			division++;
			while(!q.isEmpty()) {
				//갈 수 있을 때까지 가면서 visited[][] = true; 변경
				Node current = q.poll();
				int r = current.r;
				int c = current.c;
				char color = current.color;
//				System.out.println("poll: ("+r+", "+c+"), "+color+"!!");
				//상하좌우, 범위 내이고, 안갔고, 색이 같으면 진행
				if(r-1 >= 0 && ((color=='B'&&map[r-1][c]=='B')||(color!='B'&&map[r-1][c]!='B')) && !visited[r-1][c]) {
					q.add(new Node(r-1, c, color));
					visited[r-1][c] = true;
				}
				if(r+1 < N &&  ((color=='B'&&map[r+1][c]=='B')||(color!='B'&&map[r+1][c]!='B')) && !visited[r+1][c]) {
					q.add(new Node(r+1, c, color));
					visited[r+1][c] = true;
				}
				if(c-1 >= 0 &&  ((color=='B'&&map[r][c-1]=='B')||(color!='B'&&map[r][c-1]!='B')) && !visited[r][c-1]) {
					q.add(new Node(r, c-1, color));
					visited[r][c-1] = true;
				}
				if(c+1 < N &&  ((color=='B'&&map[r][c+1]=='B')||(color!='B'&&map[r][c+1]!='B')) && !visited[r][c+1]) {
					q.add(new Node(r, c+1, color));
					visited[r][c+1] = true;
				}
			}//현재구역 탐색 while
			
			//아직 탐색 안한 노드 추가
			search:
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						q.add(new Node(i, j, map[i][j]));
						visited[i][j] = true;
						break search;
					}
				}
			}
		}
		
		return division;
	}
	
}//class