Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 백준 4358번
- React Native
- 모두를위한딥러닝
- 모두의 네트워크
- 모두를 위한 딥러닝
- 깃허브 토큰 인증
- 깃 연동
- HTTP
- 문자열
- 깃허브 로그인
- 깃 터미널 연동
- 정리
- 자바
- 지네릭스
- 리액트 네이티브 시작하기
- 백준
- 네트워크
- 리액트 네이티브 프로젝트 생성
- 머신러닝
- 백준 5525번
- 데베
- 모두의네트워크
- 리액트 네이티브
- 데이터베이스
- 스터디
- 팀플회고
- 백준 4949번
- SQL
- 백준 4358 자바
- 딥러닝
Archives
- Today
- Total
솜이의 데브로그
백준 10026번 ) 적록색약 (java) 본문
https://www.acmicpc.net/problem/10026
문제
풀이
DFS로 탐색해나가며 주변 영역과 같은지 체크하는 문제이다.
적록색약이 아닌 사람 기준은 일반 DFS 문제로 풀면 되고, 적록색약인 경우 조건을 걸어 빨간색과 초록색을 동일하게 구분하여 영역을 카운트하도록 작성한다.
코드
import java.io.*;
import java.util.*;
public class BOJ_10026 {
static int N;
static char[][] grid;
static int[][] pictures, patient;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
pictures = new int[N][N];
patient = new int[N][N];
grid = new char[N][N];
for(int i=0; i<N; i++) {
grid[i] = br.readLine().toCharArray();
}
int cnt = 0, paitentCnt = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(pictures[i][j] == 0){
cnt++;
dfs(i, j, grid[i][j], cnt);
}
if(patient[i][j] == 0) {
paitentCnt++;
patientDFS(i, j, grid[i][j], cnt);
}
}
}
System.out.println(cnt + " " + paitentCnt);
}
static void patientDFS(int y, int x, char color, int cnt) {
patient[y][x] = cnt;
for(int i=0; i<4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX <0 || nextX >=N || nextY<0 || nextY>=N ) continue;
if(patient[nextY][nextX] != 0) continue;
char nextColor = grid[nextY][nextX];
if(nextColor == color) {
patientDFS(nextY, nextX, nextColor, cnt);
} else{
if((color == 'R' && nextColor == 'G') || (color=='G' && nextColor =='R')) {
patientDFS(nextY, nextX, nextColor, cnt);
}
}
}
}
static void dfs(int y, int x, char color, int cnt) {
pictures[y][x] = cnt;
for(int i=0; i<4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX <0 || nextX >=N || nextY<0 || nextY>=N ) continue;
if(pictures[nextY][nextX] != 0) continue;
char nextColor = grid[nextY][nextX];
if(nextColor == color) {
dfs(nextY, nextX, nextColor, cnt);
}
}
}
}
'Algorithm > 백준' 카테고리의 다른 글
백준 1253번 ) 좋다 (java) (0) | 2022.08.01 |
---|---|
백준 2293번 ) 동전 1 (java) (0) | 2022.07.23 |
백준 12931번 ) 두 배 더하기 (java) (0) | 2022.07.22 |
백준 17298번 ) 오큰수 (java) (0) | 2022.05.27 |
백준 7576번 ) 토마토 (java) (0) | 2022.03.17 |