백준 10026 - Gold 5
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서,
적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다.
(색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다.
(빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때,
적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제입력
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR예제출력
4 3
문제의 대해서 먼저 알아보자.
적록색약인 사람은 빨간색과 초록색 구분이 힘들어서 Green => Red로 바꿔서 진행하라고 되어있다.
색깔별로 구분하여서 인접된 부분들을 합쳐서 하나의 구역으로 만드는 것이 최종 목표이다.
먼저 아래의 그래프는 적록색약이 아닌 사람이 봤을 때 나뉘어진 구역이다.
인접된 부분들은 하나의 구역으로 판단하기 때문에 총 4구역으로 나뉘어진다.
| R | R | R | B | B |
| G | G | B | B | B |
| B | B | B | R | R |
| B | B | R | R | R |
| R | R | R | R | R |
하지만, 적록색약인 사람을 기준으로 구역을 나누게 되면
Green 구역이 Red로 모두 바뀌었기 때문에 총 3구역으로 나뉘어진다.
| R | R | R | B | B |
| R | R | B | B | B |
| B | B | B | R | R |
| B | B | R | R | R |
| R | R | R | R | R |
이제 코드 작성을 해볼 예정이다.
코드를 작성하기 전에 필요한 것들에 대해서 생각을 해보자
인접된 점을 찾을 때 사용하는 쉬운 방법은 2가지가 있다.
DFS / BFS이다.
나는 그 중 DFS로 코드를 구현할 예정이다.
일단 RGB / RB(적록색약)로 구분하여서 2개의 2차원 배열과
각 구역을 저장할 변수를 선언하였다.
그 후, DFS() 함수를 실행시키면서 인접한 부분이면 확인한 곳이라는
의미로 arr[i][j] = 'V'로 바꿔주면서 진행을 하였다.
가장 흔하게 사용하는 방법 중 하나는 boolean형 배열을 하나 선언한 후,
확인한 곳이면 boolean 배열에 true로 넣어주면서 넘어가는 경우도 있지만
이 문제에서는 2개의 배열을 추가해야하기 때문에, 더욱 쉽게 접근하기 위해서
2차원 배열의 값을 바꿔주는 형식으로 구현해보았다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int count1 = 0;
static int count2 = 0;
static int n = 0;
static char[][] map1;
static char[][] map2;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map1 = new char[n][n]; // RGB
map2 = new char[n][n]; // RB
// 입력 받으면서 적록색약인 사람 구분하여 2개의 테이블에 넣기
for(int i = 0;i<n;i++) {
String s = br.readLine();
for(int j = 0;j<s.length();j++) {
map1[i][j] = s.charAt(j);
if(s.charAt(j)=='G') map2[i][j] = 'R';
else map2[i][j] = s.charAt(j);
}
}
for(int i = 0;i<n;i++) {
for(int j = 0;j<n;j++) {
if(map1[i][j]!='C') {
count1++;
dfs_rgb(i,j,map1[i][j]);
}
}
}
for(int i = 0;i<n;i++) {
for(int j = 0;j<n;j++) {
if(map2[i][j]!='C') {
count2++;
dfs_rb(i,j,map2[i][j]);
}
}
}
System.out.println(count1+" "+count2);
}
public static void dfs_rgb(int x, int y, char c) {
if(x<0 || x>=n || y<0 || y>=n || map1[x][y] == 'C') return;
if((c=='R' && map1[x][y]=='R') || (c=='G' && map1[x][y]=='G') || (c=='B' && map1[x][y]=='B')) {
map1[x][y] = 'C';
for(int i = 0;i<4;i++) {
dfs_rgb(x+dx[i],y+dy[i],c);
}
}
}
public static void dfs_rb(int x, int y, char c) {
if(x<0 || x>=n || y<0 || y>=n || map2[x][y] == 'C') return;
if((c=='R' && map2[x][y]=='R') || (c=='B' && map2[x][y]=='B')) {
map2[x][y] = 'C';
for(int i = 0;i<4;i++) {
dfs_rb(x+dx[i],y+dy[i],c);
}
}
}
}
|
cs |
'백준' 카테고리의 다른 글
| 백준 11279 (Java) 최대 힙 (0) | 2023.07.03 |
|---|---|
| 백준 5430 (Java) AC (0) | 2023.06.28 |
| 백준 1920 (Java) 수 찾기 (0) | 2023.06.26 |
| 백준 9095 (Java) 1, 2, 3 더하기 (0) | 2023.06.26 |
| 백준 10816 (Java) 숫자 카드 2 (0) | 2023.06.24 |