반응형
백준 10026번 문제 - 적록색약
문제 분석
- 적록색약이 아닌 사람이 봤을 때 구역의 수와 적록색약(빨간 초록 구분 못함)이 봤을 때 구역 수를 출력해라.
해결 포인트
- BFS 구현
- 적록색약일 경우 색을 저장하는 이차원배열과, 적록색약일 경우 색을 저장하는 이차원배열을 따로 구현
- 적록색약일 경우 색을 저장하는 이차원 배열은 빨간색하고 초록색 모두 초록색으로 저장한다.
코드
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main {
public static boolean [][] visit;
public static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
char [][] colors = new char [N][N];
char [][] nonColors = new char [N][N];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
colors[i][j] = s.charAt(j);
if(colors[i][j] == 'R')
nonColors[i][j] = 'G';
else
nonColors[i][j] = colors[i][j];
}
}
visit = new boolean[N][N];
int colorCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
colorCount++;
colorBFS(new Point(i, j), colors, colors[i][j]);
}
}
}
visit = new boolean[N][N];
int nonColorCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
nonColorCount++;
colorBFS(new Point(i, j), nonColors, nonColors[i][j]);
}
}
}
bw.write(colorCount + " " + nonColorCount);
bw.flush();
bw.close();
}
public static void colorBFS(Point p, char [][] colors, char color) {
Queue<Point> queue = new LinkedList<>();
int [] dx = {0,0,1,-1};
int [] dy = {1,-1,0,0};
// char color = colors[p.x][p.y];
visit[p.x][p.y] = true;
queue.add(p);
while (!queue.isEmpty()) {
Point newP = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = newP.x + dx[i];
int nextY = newP.y + dy[i];
if(checkRound(nextX, nextY) && color==colors[nextX][nextY] && !visit[nextX][nextY]) {
visit[nextX][nextY] = true;
queue.add(new Point(nextX, nextY));
}
}
}
}
public static boolean checkRound(int x, int y) {
return x >= 0 && y>=0 && x < N && y < N;
}
}
반응형
'CodingTEST' 카테고리의 다른 글
[백준 1107] 리모컨(JAVA) (1) | 2024.01.02 |
---|---|
[백준 16928] 뱀과 사다리 게임(JAVA) (1) | 2024.01.02 |
[백준 6064] 카잉 달력 (JAVA) (1) | 2023.12.28 |
[백준 1389] 케빈 베이컨의 6단계 법칙 (JAVA) (1) | 2023.12.28 |
[백준 20529] 가장 가까운 세 사람의 심리적 거리 (JAVA) (1) | 2023.12.26 |