🔗 문제 링크
https://www.acmicpc.net/problem/10026
📝 문제풀이 방법
해당 문제도 앞서 풀었던 백준 1987 알파벳문제와 같이 주어진 배열을 BFS 또는 DFS를 통해 탐색을 하며 풀이를 하면 되는 문제이다.
단, 적록색약인 사람과 정상인인 사람의 조건이 달라 두개의 조건을 만들어 두번의 탐색을 돌려야한다.
처음에는 문제를 BFS를 통해 코드를 작성했다. 아래 첨부한 BFS 코드는 이클립스 내에서 결과는 잘 나왔으나 백준에서 실행을 돌렸을 때 메모리 초과로 통과를 하지 못하였다..😥
메모리 사용량을 줄이려고 많은 변경을 시도했으나 계속 같은 결과가 나와서 DFS로 코드를 다시 작성하니 문제를 통과할 수 있었습니다.
👨🏻💻 BFS로 작성한 코드 (메모리 초과..)
import java.io.*;
import java.util.*;
public class Main {
static char[][] matrix;
static int N;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
matrix = new char[N][N];
boolean[][] isChecked1 = new boolean[N][N]; // 정상인의 탐색여부 체크
boolean[][] isChecked2 = new boolean[N][N]; // 정록색약의 탐색 체크
for (int i=0; i<N; i++) {
matrix[i] = br.readLine().toCharArray();
}
int result1 = 0;
int result2 = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (!isChecked1[i][j]) {
result1++;
bfs(i, j, true, isChecked1);
}
if (!isChecked2[i][j]) {
result2++;
bfs(i, j, false, isChecked2);
}
}
}
bw.write(result1+" "+result2);
bw.flush();
bw.close();
br.close();
}
// 정상인은 normal이 true, 정록색약은 false
static void bfs(int r, int c, boolean normal, boolean[][] isChecked) {
Queue<Integer> queue = new LinkedList<>();
boolean[] available; // 현재 위치에서 상하좌우로 가능한지를 나타내는 변수
queue.add(r);
queue.add(c);
while(!queue.isEmpty()) {
int row = queue.poll();
int column = queue.poll();
if (normal) available = isAvailable1(row, column);
else available = isAvailable2(row, column);
isChecked[row][column] = true;
if (available[0] && !isChecked[row-1][column]) {
queue.add(row-1);
queue.add(column);
}
if (available[1] && !isChecked[row+1][column]) {
queue.add(row+1);
queue.add(column);
}
if (available[2] && !isChecked[row][column-1]) {
queue.add(row);
queue.add(column-1);
}
if (available[3] && !isChecked[row][column+1]) {
queue.add(row);
queue.add(column+1);
}
}
}
// 정상인 경우
static boolean[] isAvailable1(int r, int c) {
boolean[] available = new boolean[4];
if (-1 < (r-1) && matrix[r][c] == matrix[r-1][c]) // 위로 이동
available[0] = true;
if ((r+1) < N && matrix[r][c] == matrix[r+1][c]) // 아래로 이동
available[1] = true;
if (-1 < (c-1) && matrix[r][c] == matrix[r][c-1]) // 왼쪽으로 이동
available[2] = true;
if ((c+1) < N && matrix[r][c] == matrix[r][c+1]) // 오른쪽로 이동
available[3] = true;
return available;
}
// 정록색약인 경우
static boolean[] isAvailable2(int r, int c) {
boolean[] available = new boolean[4];
if (-1 < (r-1)) {// 위로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r-1][c] == 'R' || matrix[r-1][c] == 'G')
available[0] = true;
}
else if (matrix[r][c] == matrix[r-1][c]) available[0] = true;
}
if ((r+1) < N) { // 아래로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r+1][c] == 'R' || matrix[r+1][c] == 'G')
available[1] = true;
}
else if (matrix[r][c] == matrix[r+1][c]) available[1] = true;
}
if (-1 < (c-1)) { // 왼쪽으로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r][c-1] == 'R' || matrix[r][c-1] == 'G')
available[2] = true;
}
else if (matrix[r][c] == matrix[r][c-1]) available[2] = true;
}
if ((c+1) < N) {// 오른쪽로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r][c+1] == 'R' || matrix[r][c+1] == 'G')
available[3] = true;
}
else if (matrix[r][c] == matrix[r][c+1]) available[3] = true;
}
return available;
}
}👨🏻💻 DFS로 작성한 코드 (통과)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static char[][] matrix;
static int N;
static boolean[][] isChecked;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
matrix = new char[N][N];
isChecked = new boolean[N][N]; // 탐색여부 체크
for (int i=0; i<N; i++) {
matrix[i] = br.readLine().toCharArray();
}
int result = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (!isChecked[i][j]) {
result++;
dfs(i, j, true);
}
}
}
bw.write(result+" ");
isChecked = new boolean[N][N];
result = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (!isChecked[i][j]) {
result++;
dfs(i, j, false);
}
}
}
bw.write(result+"");
bw.flush();
bw.close();
br.close();
}
static void dfs(int row, int column, boolean normal) {
isChecked[row][column] = true;
// System.out.println("check "+ row+" "+ column);
boolean allFalse = true;
boolean[] available; // 현재 위치에서 상하좌우로 가능한지를 나타내는 변수
if (normal) available = isAvailable1(row, column);
else available = isAvailable2(row, column);
if (available[0] && !isChecked[row-1][column]) {
allFalse = false;
dfs(row-1, column, normal);
}
if (available[1] && !isChecked[row+1][column]) {
allFalse = false;
dfs(row+1, column, normal);
}
if (available[2] && !isChecked[row][column-1]) {
allFalse = false;
dfs(row, column-1, normal);
}
if (available[3] && !isChecked[row][column+1]) {
allFalse = false;
dfs(row, column+1, normal);
}
}
// 정상인 경우
static boolean[] isAvailable1(int r, int c) {
boolean[] available = new boolean[4];
if (-1 < (r-1) && matrix[r][c] == matrix[r-1][c]) // 위로 이동
available[0] = true;
if ((r+1) < N && matrix[r][c] == matrix[r+1][c]) // 아래로 이동
available[1] = true;
if (-1 < (c-1) && matrix[r][c] == matrix[r][c-1]) // 왼쪽으로 이동
available[2] = true;
if ((c+1) < N && matrix[r][c] == matrix[r][c+1]) // 오른쪽로 이동
available[3] = true;
return available;
}
// 정록색약인 경우
static boolean[] isAvailable2(int r, int c) {
boolean[] available = new boolean[4];
if (-1 < (r-1)) {// 위로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r-1][c] == 'R' || matrix[r-1][c] == 'G')
available[0] = true;
}
else if (matrix[r][c] == matrix[r-1][c]) available[0] = true;
}
if ((r+1) < N) { // 아래로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r+1][c] == 'R' || matrix[r+1][c] == 'G')
available[1] = true;
}
else if (matrix[r][c] == matrix[r+1][c]) available[1] = true;
}
if (-1 < (c-1)) { // 왼쪽으로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r][c-1] == 'R' || matrix[r][c-1] == 'G')
available[2] = true;
}
else if (matrix[r][c] == matrix[r][c-1]) available[2] = true;
}
if ((c+1) < N) {// 오른쪽로 이동
if (matrix[r][c] == 'R' || matrix[r][c] == 'G') {
if (matrix[r][c+1] == 'R' || matrix[r][c+1] == 'G')
available[3] = true;
}
else if (matrix[r][c] == matrix[r][c+1]) available[3] = true;
}
return available;
}
}
상단에 위치한 결과는 DFS 코드의 결과이며 아래에 위치한 결과는 BFS의 결과입니다.
블로그 이전했습니다. -> https://seongwon.dev/