백준 10026번 : 적록색약

문제풀이

• 접근법 : BFS

• 풀이과정

  1. 그림 배열을 전체 순회하면서, 아직 방문하지 않은 구역을 시작점으로 설정하고, 인접한 구역 중에서 해당 구역의 색깔과 동일한 구역을 계속해서 큐에 넣으면서 BFS를 수행한다.
     ⇒ 적록색약이 아닌 사람이 보는 구역의 개수 구하기
  2. 만약 적록색약 확인용으로도 방문하지 않은 구역이고 빨간색 또는 초록색이면, 해당 구역을 시작점으로 설정하고 인접한 빨간색 또는 초록색 구역을 계속해서 큐에 넣으면서 BFS를 수행한다.
     ⇒ 적록색약인 사람이 보는 구역의 개수 구하기

java 구현 코드

package ch08_BFS;

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

public class p10026 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.valueOf(br.readLine());
		
		int[] dx = {1,0,-1,0};
		int[] dy = {0,1,0,-1};
		
		char[][] picture = new char[N][N];  // 그림 배열
		boolean[][] visited = new boolean[N][N];  // 적록색약 X 방문 여부 표시 배열
		boolean[][] visited_RG = new boolean[N][N];  // 적록색약 O 방문 여부 표시 배열
		
		Queue<Point> queue = new LinkedList<>();  // 큐 생성
		
		int count = 0;  // 적록색약 X 구역의 개수
		int RG = 0;  // 적록색약 O 구역의 개수 
		int B = 0;  // B의 개수 
		
		
		/*
		 * 그림 배열 값 세팅
		 */
		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			for (int j = 0; j < N; j++) {
				picture[i][j] = input.charAt(j);
			}
		}
		
		/*
		 * 그림 배열 전체 순회하면서, 방문하지 않은 구역을 시작점으로 BFS 수행
		 */
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				/*
				 * 적록색약 X에 대한 BFS
				 */
				if (visited[i][j] == true) continue;  // 방문 여부 검증 
				queue.add(new Point(i, j));  // enqueue
				visited[i][j] = true;  // 방문 표시
				count++;
				
				char color = picture[i][j];  // 시작점의 색깔 color 
				if (color == 'B') B++;
				
				while (!queue.isEmpty()) {
					Point dequeue = queue.remove();  // dequeue
					
					for (int d = 0; d < 4; d++) {
						int dX = dequeue.X + dx[d];
						int dY = dequeue.Y + dy[d];
						
						if (dX < 0 || dX >= N || dY < 0 || dY >= N || visited[dX][dY] == true) continue;  // 좌표 유효성 검증, 방문 여부 검증 
					    if (picture[dX][dY] != color) continue;  // 시작점의 색깔과 비교
					    queue.add(new Point(dX, dY));  // enqueue
					    visited[dX][dY] = true;  // 방문 표시
					}
				}
				
				/*
				 * 적록색약 O에 대한 BFS
				 */
				if (visited_RG[i][j] == true || picture[i][j] == 'B') continue;  // 방문 여부, 색깔 검증 
				queue.add(new Point(i, j));  // enqueue
				visited_RG[i][j] = true;  // 방문 표시
				RG++;
				
				while (!queue.isEmpty()) {
					Point dequeue = queue.remove();  // dequeue
					
					for (int d = 0; d < 4; d++) {
						int dX = dequeue.X + dx[d];
						int dY = dequeue.Y + dy[d];
						
						if (dX < 0 || dX >= N || dY < 0 || dY >= N || visited_RG[dX][dY] == true) continue;  // 좌표 유효성 검증, 방문 여부 검증 
					    if (picture[dX][dY] == 'B') continue;  // 시작점의 색깔과 비교
					    queue.add(new Point(dX, dY));  // enqueue
					    visited_RG[dX][dY] = true;  // 방문 표시
					}
				}
			}
		}
		System.out.println(count + " " + (RG + B));
	}
}

class Point {
	int X;
	int Y;
	
	Point(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
}

comment

• 풀이 날짜 : 2312어느날, 240101

저번에 풀었다가 해결 못한 문제를 오늘 끝내 해결했다.
2024년에 처음으로 해결한 문제다. 2024년 시작이 좋다! 🍀

2024년 2월 6일 복습 코드

package review;

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

public class p1926 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int n = Integer.valueOf(st.nextToken());  // 세로
		int m = Integer.valueOf(st.nextToken());  // 가로
		
		int[][] picture = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < m; j++) {
				picture[i][j] = Integer.valueOf(st.nextToken());
			}
		}

		int[] dx = {0, 0, -1, 1};
		int[] dy = {1, -1, 0, 0};
		
		int count = 0;
		int maxSize = 0;
		
		boolean visited[][] = new boolean[n][m];
		Queue<Point> queue = new LinkedList<>();
		
		for (int i = 0 ; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j] && picture[i][j] == 1) {
					int size = 1;
					count++;
					
					queue.add(new Point(i, j));
					visited[i][j] = true;
					
					while (!queue.isEmpty()) {
						Point dequeue = queue.remove();
						
						for (int d = 0; d < 4; d++) {
							int dX = dequeue.X + dx[d];
							int dY = dequeue.Y + dy[d];
							
							if (dX < 0 || dX >= m || dY < 0 || dY >= n) continue;
							
							if (!visited[dY][dX] && picture[dY][dX] == 1) {
								queue.add(new Point(dX, dY));
								visited[dY][dX] = true;
								size++;
							}
						}
					}
					maxSize = (size > maxSize) ? size : maxSize;
				}
			}
		}
		System.out.println(count + "\n" + maxSize);
	}
}

class Point {
	int X;
	int Y;
	
	Point(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
}