https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
이렇게 풀어도 되는걸까,,? 라는 생각으로 물음표 가득 띄운채 풀었는데 시간도 메모리도 엄청 여유롭게 통과해서 놀랐다😮😮😮
이런 방식으로 풀면 답은 나오겠다 싶긴 했지만 같은 과정을 여러번 반복하는 느낌이라서 시간이든 메모리든 초과가 나올 줄 알았다 글 작성하고나서 다른 사람들의 풀이를 찾아볼 예정,,
DFS 알고리즘을 이용하였고 문자별로 각각 카운트해주었다
전체 grid 배열을 돌면서
- R 만남 → checkR → 이어져있는 R 구역을 확인하고, 확인한 R은 Z로 바꿔서 다시 방문하지 않도록 함 → 이어진 R을 모두 확인한 후 돌아와서 r 값을 하나 더해줌 (R구역을 하나 확인했다는 의미)
- G 만남 → checkG → 이어져있는 G 구역을 확인하고, 확인한 G는 Z로 바꿔서 다시 방문하지 않도록 함 → 이어진 G를 모두 확인한 후 돌아와서 g 값을 하나 더해줌 (G구역을 하나 확인했다는 의미)
⭐ R과 G를 같은 문자로 바꿔준 이유는 나중에 하나의 색으로 계산하기 위함이다 ( 적록색약은 R, G 두개의 색을 같은 색으로 보기 때문에)
- B 만남 → checkB → 이어져있는 B 구역을 확인하고, 확인한 B는 C로 바꿔서 다시 방문하지 않도록 함 → 이어진 B 를 모두 확인한 후 돌아와서 b 값을 하나 더해줌 ( B구역을 하나 확인했다는 의미)
적록색약인 사람이 보는 것도 확인해야하기 때문에 R과 G를 묶은 Z를 확인하기 위해 전체 배열을 한번 더 돌아줌
- Z 만남 → checkRG → 이어져있는 Z 구역을 확인하고, 확인한 Z는 Y로 바꿔서 다시 방문하지 않도록 함 → 이어진 Z를 모두 확인한 후 돌아와서 rg 값을 하나 더해줌 (Z구역을 하나 확인했다는 의미)
모두 확인했으면 최종 답을 계산해주면 된다
- 적록색약이 아닌 사람 : result1 = r + g + b
- 적룍색약인 사람 : result2 = rg + b
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N;
static String[][] grid;
static int r = 0;
static int g = 0;
static int rg = 0;
static int b = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
grid = new String[N][N];
for(int i = 0; i < N; i++) {
String[] str = br.readLine().split("");
for(int j = 0; j < N; j++) {
grid[i][j] = str[j];
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if (grid[i][j].equals("R")) {
checkR(i, j);
r++;
}
else if(grid[i][j].equals("G")) {
checkG(i, j);
g++;
}
else if(grid[i][j].equals("B")) {
checkB(i, j);
b++;
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(grid[i][j].equals("Z")) {
checkRG(i, j);
rg++;
}
}
}
int result1 = r + g + b;
int result2 = rg + b;
System.out.println(result1 + " " + result2);
}
static void checkR(int x, int y) {
grid[x][y] = "Z";
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny].equals("R")) checkR(nx, ny);
}
}
}
static void checkG(int x, int y) {
grid[x][y] = "Z";
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny].equals("G")) checkG(nx, ny);
}
}
}
static void checkB(int x, int y) {
grid[x][y] = "C";
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny].equals("B")) checkB(nx, ny);
}
}
}
static void checkRG(int x, int y) {
grid[x][y] = "Y";
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny].equals("Z")) checkRG(nx, ny);
}
}
}
}
한문제만 더 풀면 실버2로 올라갈듯!! 골드로 빨리 가고싶다🏃♂️🏃♀️🏃♂️🏃♀️
+
2024.02.28
코테 스터디를 하면서 깨달은 내용
- 한글자씩 쓰이는 경우에는 String 배열이 아니라 char 배열이 훨씬훨씬좋다!!!!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N;
static char[][] grid;
static int r = 0;
static int g = 0;
static int rg = 0;
static int b = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
grid = new char[N][N];
for(int i = 0; i < N; i++) {
String str = br.readLine();
for(int j = 0; j < N; j++) {
grid[i][j] = str.charAt(j);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if (grid[i][j] == 'R') {
checkR(i, j);
r++;
}
else if(grid[i][j] == 'G') {
checkG(i, j);
g++;
}
else if(grid[i][j] == 'B') {
checkB(i, j);
b++;
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(grid[i][j] == 'Z') {
checkRG(i, j);
rg++;
}
}
}
int result1 = r + g + b;
int result2 = rg + b;
System.out.println(result1 + " " + result2);
}
static void checkR(int x, int y) {
grid[x][y] = 'Z';
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny] == 'R') checkR(nx, ny);
}
}
}
static void checkG(int x, int y) {
grid[x][y] = 'Z';
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny] == 'G') checkG(nx, ny);
}
}
}
static void checkB(int x, int y) {
grid[x][y] = 'C';
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny] == 'B') checkB(nx, ny);
}
}
}
static void checkRG(int x, int y) {
grid[x][y] = 'Y';
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny] == 'Z') checkRG(nx, ny);
}
}
}
}
String 배열로 풀었을 때:
char 배열로 풀었을 때:
'코딩테스트-알고리즘 > 백준 BOJ' 카테고리의 다른 글
| [백준 BOJ/Silver I] 1697번 : 숨바꼭질 (0) | 2024.02.20 |
|---|---|
| [백준 BOJ/Silver II] 11724번 : 연결 요소의 개수 (0) | 2024.02.15 |
| [백준 BOJ/Bronze III] 2501번 : 약수 구하기 (1) | 2024.02.11 |
| [백준 BOJ/Gold V] 12904번 : A와 B (0) | 2024.02.10 |
| [백준 BOJ/Gold V] 7576번 : 토마토 (0) | 2024.02.09 |