728x90
🔗 문제 링크
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
💡 문제 풀이 및 해석
- 평범한 BFS 문제로 본다면, 모든 지점에서 BFS 알고리즘을 구현하여 실행하면 된다.
- 적록색약과 아닌 상황을 구분해야 하므로, 아래와 같은 과정을 거쳐야 한다.
3-1. 적록색맹이 아닌 사람에 대해서 BFS로 검사한다.
3-2. 적록색맹인 사람은 R -> G 로 바꿔서 검사한다.
⭐️ 정답 코드 및 설명
import javax.naming.PartialResultException;
import java.awt.image.ImageProducer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Main {
static int N;
static String str;
static char[][] arr;
static boolean[][] visit;
static int[] next_x = {-1, 1, 0, 0};
static int[] next_y = {0, 0, 1, -1};
static int rgbAnswer = 0;
static int noRgbAnswer = 0;
public static void main(String[] args) throws IOException {
BufferedReader init = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(init.readLine());
arr = new char[N][N];
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
str = init.readLine();
for (int j = 0; j < N; j++) {
arr[i][j] = str.charAt(j);
}
}
int cnt = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (!visit[y][x]) {
BFS(x, y);
cnt++;
}
}
}
System.out.printf("%d ", cnt);
// 방문 초기화
cnt = 0;
visit = new boolean[N][N];
// 적록색맹은 구별하지 못하는 색
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (arr[y][x] == 'R') {
arr[y][x] = 'G';
}
}
}
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (!visit[y][x]) {
BFS(x, y);
cnt++;
}
}
}
System.out.println(cnt);
}
public static void BFS(int x, int y) {
LinkedList<int[]> list = new LinkedList<>();
list.add(new int[]{x, y});
visit[y][x] = true;
while (!list.isEmpty()) {
// 현재 좌표
int curx = list.getFirst()[0];
int cury = list.getFirst()[1];
list.removeFirst(); // 현재위치 추출 완료
for (int i = 0; i < 4; i++) {
// 상하 좌우
int nx = curx + next_x[i];
int ny = cury + next_y[i];
// 다음 좌표가 범위안에 있고, 방문하지 않은 곳인가?
if (nx > -1 && ny > -1 && nx < N && ny < N && !visit[ny][nx]) {
// 색이 같다면
if (arr[cury][curx] == arr[ny][nx]) {
visit[ny][nx] = true; // 방문표시
list.add(new int[]{nx, ny}); // 여기서도 찾아보자
}
}
}
}
}
}
🤔 문제 후기
처음에는 문제를 풀 때, 초록색을 빨간색으로 바꾼다는 생각보다는 적록색맹인 경우와 아닌 경우로 나누었는데, 생각보다 복잡해져서 다시 문제를 풀면서 아예 맵을 바꿔버리면 굳이 구분을 안해도 되는 것을 알고 바꿨다. 이 부분이 코드를 구현하는 시간을 많이 단축시켜주었다고 생각한다. 그 외의 점은 일반적인 BFS문제 여서 크게 어렵지 않았다.
728x90
'문제풀이 > 알고리즘 문제 풀이' 카테고리의 다른 글
[ 백준 2631 ] 줄 세우기 (Java) - DP (0) | 2024.03.09 |
---|---|
[ 프로그래머스 ] 파괴되지 않은 건물 (C++) - 누적합 (0) | 2024.03.09 |
[ 백준 2194 ] 유닛 이동시키기 (C++) - BFS (0) | 2024.03.09 |
[ 백준 13424 ] 비밀 모임 (C++) - Dijkstra (0) | 2024.03.09 |
[ 백준 20058 ] 마법사 상어와 파이어스톰 (C++) - 구현, 시뮬레이션 (1) | 2024.03.08 |