문제링크
접근한 방법
- 구역을 구하는 문제이므로
dfs
풀이방법
두 가지 경우를 나누어 탐색을 수행한다.
1) 적록색약이 아닌 경우 : R, G, B 구역
2) 적록색약인 경우 : R 또는 G, B 구역
1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 탐색하는 지점의 문자가 R, G, B중 적록색약일 경우와 아닌 경우에 따라 (아래 참조) 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 적록색약이 아닌 사람일 경우 현재 탐색중인 문자와 같을 때(e.g. 현재 탐색중인 문자가 R이라면 R만 탐색)만 탐색
- 적록색약일 경우 현재 탐색중인 문자가 R이거나 G라면 R과 G인 경우도 포함하여 탐색
2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
방문시마다 요소의 수를 더해준다.
3. 1~2번의 과정을 모든 노드에 반복
소스코드 작성 방법
- 맵의 크기(n)를 전역 필드로 선언한다.
- 그림의 정보(map), 방문 여부(visitied1, visited2)는 두가지 경우를 나누어 전역 필드로 선언한다.
- 각 영역의 개수(count1, count2)를 전역 필드로 선언한다.
- 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
- dfs 메소드를 적록색약인 경우와 적록색약이 아닐 경우 2가지를 선언한다.
- dfs 메소드 공통으로 인자를 노드 번호(curR, curC)와 현재 탐색하고 있는 문자(c)를 받는다.
- vistied[curR][curC] = true로 하여 방문 처리
- 방문할 때 마다 count++하여 집의 개수를 추가한다.
- nextR, nextC를 for문 안에 선언하여 현재 위치에서 상 좌 하 우 위치를 탐색한다.
- nextR은 curR + dx[dir]
nextC는 curC + dx[dir] 로 상 좌 하 우 값을 선언해준다. - 상 좌 하 우 위치 이동 시 n*n배열의 크기보다 크면 continue하여 넘어간다.
- nextR은 curR + dx[dir]
- 1) 적록색약이 아닌 경우 - 현재 탐색중인 문자와 같은 값을 가져야 탐색 진행
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
dfs 메소드를 재귀적으로 호출하여 방문수행
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
- 2) 적록색약인 경우 - 현재 탐색중인 문자가 R이나 G라면 R과 G 값을 가진 경우도, B라면 B값을 가진 경우만 탐색 진행
- 탐색중인 값이 R이나 G일 때)
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
dfs 메소드를 재귀적으로 호출하여 방문수행
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
- 탐색중인 값이 B일 때)
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
dfs 메소드를 재귀적으로 호출하여 방문수행
- map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
- 탐색중인 값이 R이나 G일 때)
- solution 메소드에서 (0,0) 노드부터 (n-1,n-1)노드까지 탐색을 수행한다.
- dfs 메소드가 끝날때마다 count를 ++ 해준다.
소스코드
package baekjoon.dfs_bfs;
import java.io.*;
public class Q_10026_ColorWeakness_20210523 {
public static int n;
public static char[][] map;
public static boolean[][] visited1; // 적록색약이 아닌 사람 방문 체크
public static boolean[][] visited2; // 적록색약인 사람 방분 체크
public static int count1, count2; // 결과
// 상좌하우
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, -1, 0, 1};
public static void solution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!visited1[i][j]){
dfs1(i, j, map[i][j]);
count1++;
}
if(!visited2[i][j]){
dfs2(i, j, map[i][j]);
count2++;
}
}
}
}
// 적록색약이 아닌 사람 체크 - R, G, B 구역
public static void dfs1(int curR, int curC, char c){
visited1[curR][curC] = true;
for (int i = 0; i < 4; i++) {
int nextR = curR + dx[i];
int nextC = curC + dy[i];
if(nextR <0 || nextC <0 || nextR >=n || nextC >=n) continue;
else if(map[nextR][nextC] == c && !visited1[nextR][nextC]){
dfs1(nextR, nextC, c);
}
}
}
// 적록색약인 사람 체크 - RG, B 구역
public static void dfs2(int curR, int curC, char c){
visited2[curR][curC] = true;
for (int i = 0; i < 4; i++) {
int nextR = curR + dx[i];
int nextC = curC + dy[i];
if(nextR <0 || nextC <0 || nextR >=n || nextC >=n) continue;
else{
if(c == 'B'){
if(map[nextR][nextC] == 'B' && !visited2[nextR][nextC])
dfs2(nextR, nextC, c);
} else {
if((map[nextR][nextC] == 'R' || map[nextR][nextC] == 'G') && !visited2[nextR][nextC])
dfs2(nextR, nextC, c);
}
}
}
}
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());
map = new char[n][n];
visited1 = new boolean[n][n];
visited2 = new boolean[n][n];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < n; j++) {
map[i][j] = str.charAt(j);
}
}
solution();
bw.write(count1+" "+count2);
br.close();
bw.close();
}
}
반응형
'자료구조&알고리즘 > DFS BFS' 카테고리의 다른 글
[백준] dfs/bfs - 1260번 DFS와 BFS(Java) (0) | 2021.06.30 |
---|---|
[백준] dfs - 2648번 안전영역 (Java) (0) | 2021.06.14 |
[백준] dfs - 2583번 영역 구하기 (Java) (0) | 2021.05.23 |
[백준] dfs - 2667번 단지번호붙이기 (Java) (0) | 2021.05.22 |
[백준] dfs - 1743번 음식물 피하기 (Java) (0) | 2021.05.21 |
댓글