[BOJ] 10026번 적록색약(Java)
문제
풀이
같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로,
깊이우선탐색을 통해 같은 구역을 확인한다.
문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|`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로 바꿔 적록색약 검사를 위해 셋팅한다.
}
}
Author And Source
이 문제에 관하여([BOJ] 10026번 적록색약(Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-10026번-적록색약Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)