[BOJ]10026号赤色薬水(Java)
質問する
10026号:赤い薬
に答える
同じ色の上下左右が隣接している場合は、同じ色となります.
深さ優先探索により同じ領域を決定します.
問題は「同じ色が上下左右に隣接している」ということなので、上下左右が隣接しているはずだと思いますが…┗|`O′|┛
一般人が見ているエリアを確認するために入力順にDFSを回します.
DFSの回転中にG色が発生すると、インデックスのすべての演算が終了してからRに変換されます.
赤い薬水の時の探索のために!
そして、再び同じ方法で赤いDFSを回転させ、結果を出力する.
コード#コード#
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
static int[] di = {-1,1,0,0};
static int[] dj = {0,0,-1,1};
static int N;
static char[][] color;
static boolean[][] visited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
color = new char[N][N];
visited = new boolean[N][N];
int res = 0;
for(int i =0 ; i < N ; i++) {
String str = br.readLine();
for(int j =0 ; j < N ; j++) {
color[i][j] = str.charAt(j);
}
}
//적록색약이 아닐 때, 구역 개수
for(int i =0 ; i < N ; i++) {
for(int j =0 ; j < N ; j++) {
if(!visited[i][j]) {
area(i,j);
res++;
}
}
}
sb.append(res).append(" ");
res = 0;
visited = new boolean[N][N];
//적록색약일 때, 구역 개수
for(int i =0 ; i < N ; i++) {
for(int j =0 ; j < N ; j++) {
if(!visited[i][j]) {
area(i,j);
res++;
}
}
}
sb.append(res);
System.out.println(sb.toString());
}
public static void area(int i, int j) { //깊이우선탐색
visited[i][j] = true;
for(int d = 0; d< 4; d++) {
int ni = i + di[d];
int nj = j + dj[d];
if(0<=ni && ni<N && 0<=nj && nj<N && !visited[ni][nj] && color[i][j] == color[ni][nj]) {
area(ni, nj);
}
}
if(color[i][j] == 'G') color[i][j] = 'R'; //일반인 > 적록색약 순으로 검사하므로 일반인 검사 시에 G을 다 R로 바꿔 적록색약 검사를 위해 셋팅한다.
}
}
Reference
この問題について([BOJ]10026号赤色薬水(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-10026번-적록색약Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol