문제는 다음과 같다.
https://www.acmicpc.net/problem/10026
흔한 BFS 문제이다.
물론 문제를 읽고 이해하는 내용도 중요하지만
바쁜 현대인들을 위해 예시 입출력을 설명하자면,
적록색약이 아닐때는 R G B가 구분가능하므로 아래와 같이 4구간으로 나뉜다.
적록색약일때는 RG와 B만 구분가능하므로 아래와 같이 3구간으로 나뉜다.
그렇게 출격값은 각각 정상인 구간, 적록색약 구간 으로
4 3 인 것이다.
풀이는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int n; //n x n 행렬
static char[][] p; //픽처, 그림이다. 각각 R, G, B가 들어간다
static int[] dr = {-1, 1, 0, 0}; //상하좌우 순서
static int[] dc = {0, 0, -1, 1};
static boolean[][] v; //방문 체크 배열
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//적록색약.
//적록색약인 사람은 RG와 B로
//아닌 양반들은 R G B 로 각각 BFS돌려주고, 돌린 후 뭉탱이의 개수를 적어주면 된다.
n = Integer.parseInt(br.readLine());
p = new char[n][n];
for(int i = 0 ; i < n ; i++) { //행마다 char[]으로 만들어서 대입하기
p[i] = br.readLine().toCharArray();
//예를 들어, 첫행 RRRBB -> {R, R, R, B, B} 가 p의 0행이다.
}
//여기까지 초깃값 설정
//적록색맹이 아닐때, 적록색맹일때 두번 돌아줄 예정이다.
//내가 생각하는 로직 -> p의 모든 점을 돌며 방문하지 않았다면, BFS를 실행한다.
//BFS는 색에 따라 이동하며, 이동한 부분은 v로 체크해준다.
//예를 들어, 아래와 같은 p 배열일때, 0행 0열을 시작으로 BFS를 돌아본다고 하자.
//RRRBB
//GGBBB
//BBBRR
//BBRRR
//RRRRR
//0행 0열은 방문이전이므로, BFS가 돌아가게 되고, 색은 R이므로 같은 R만 순회하게 된다.
//0행 0열 BFS이후 방문된 부분을 지워준다고 표현하면, 아래와 같다.
// BB
//GGBBB
//BBBRR
//BBRRR
//RRRRR
//위 예시는 적록색맹이 아닐때의 예시이고, 적록색맹일때는 위의 로직에서,
//적록, 즉 R과 G를 같은 색상이라고 생각하고 로직을 짜주면 된다.
//자세한 내용은 아래와 같다.
v = new boolean[n][n];
int ans1 = 0; //정상 구역 나누기
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(!v[i][j]) {
bfs(i, j);
ans1++; //정상인 구역 하나당 ans1++
}
}
}
v = new boolean[n][n]; //이미 위에서 사용해서 전부 true가 되었으므로, 다시 선언해주기
int ans2 = 0; //적록색맹 구역 나누기
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(!v[i][j]) {
bfs1(i, j);
ans2++; //적록색맹인 분 구역 하단당 ans2++;
}
}
}
bw.write(String.valueOf(ans1) + " " + String.valueOf(ans2));
bw.flush();
bw.close();
}
static void bfs(int r, int c) { //bfs는 정상 bfs
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r, c});
v[r][c] = true;
char color = p[r][c]; //뽑아낸 색
while(!q.isEmpty()) {
int[] cur = q.poll();
int curR = cur[0];
int curC = cur[1];
for(int i = 0 ; i < 4 ; i++) {
int nR = curR + dr[i];
int nC = curC + dc[i];
if(isValid(nR, nC) && p[nR][nC] == color) {
//인덱스 유효하고, 이동할 색이 기존에 뽑은 색과 같다면 bfs 진행
v[nR][nC] = true;
q.add(new int[] {nR, nC});
}
}
}
}
static void bfs1(int r, int c) { //bfs1은 적록색약 bfs
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r, c});
v[r][c] = true;
char color = p[r][c];
//뽑아낸 색이 B라면 B만 탐색하고,
//나머지 RG라면 적록색약이므로 같은 색으로 인식하고 탐색해야 한다.
if(color == 'B') { //뽑아낸 색이 B라면 이동할 부분은 B여야 하고, 해당 로직은 아래에
while(!q.isEmpty()) {
int[] cur = q.poll();
int curR = cur[0];
int curC = cur[1];
for(int i = 0 ; i < 4 ; i++) {
int nR = curR + dr[i];
int nC = curC + dc[i];
if(isValid(nR, nC) && p[nR][nC] == 'B') { //이동할 부분은 B여야 함
v[nR][nC] = true;
q.add(new int[] {nR, nC});
}
}
}
}
else { //적록색맹, RG를 같은 색으로 인식해주기
while(!q.isEmpty()) {
int[] cur = q.poll();
int curR = cur[0];
int curC = cur[1];
for(int i = 0 ; i < 4 ; i++) {
int nR = curR + dr[i];
int nC = curC + dc[i];
if(isValid(nR, nC)) {
if(p[nR][nC] == 'R' || p[nR][nC] == 'G') { //이동할 부분은 적(R) 혹은 록(G) 이면 됨
v[nR][nC] = true;
q.add(new int[] {nR, nC});
}
}
}
}
}
}
static boolean isValid(int r, int c) { //주어진 index가 유효한 인덱스인지 판별
if(r < 0 || r >= n || c < 0 || c >= n || v[r][c]) return false;
return true;
}
}코드를 보며 어지럽고 헷갈리신다면,
아래의 내용만 집중해서 읽어보시면 이해가 가실것이다.
적록색맹이 아닐때, 적록색맹일때 BFS를 두번 돌아줄 예정이다.
내가 생각하는 로직 -> char[][] p의 모든 점을 돌며 방문하지 않았다면, BFS를 실행한다.
BFS는 색에 따라 같은 색으로 인식할때 이동하며,
이동한 부분은 v[r][c] = true로 체크해준다.
문제 입출력의 예시를들어, 아래와 같은 p 배열일때,
0행 0열을 시작으로 BFS를 돌아본다고 하자.
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
0행 0열은 방문이전이므로, BFS가 돌아가게 되고, 색은 R이므로 같은 R만 순회하게 된다.
0행 0열 BFS이후 방문된 부분을 x로 표현하면, 아래와 같다.
xxxBB
GGBBB
BBBRR
BBRRR
RRRRR
다음 로직은 0행 3열 차례에서 B 구간을 탐색해주는것이다.
이렇게 탐색이 마무리되면, 구간이 몇개인지 구할 수 있다.
위 예시는 적록색맹이 아닐때의 예시이고, 적록색맹일때는 위의 로직에서,
적록, 즉 R과 G를 같은 색상이라고 생각하고 로직을 짜주면 된다.
(내 코드의 bfs1(r, c) 매서드가 적록색맹 전용 BFS)
핵심 로직은 이와 같고,
코드를 짜며 상세한 내용은 주석처리를 통해 설명을 적어놓았다!
모르는 내용이 있거나 틀린 내용이 있으면,
마음 편하게 말씀해주시면 감사하겠습니다!
