[백준 10026] 적록색약 / 자바 / 그래프 순회(dfs)

문제         

레벨: G2
알고리즘: DFS 
풀이시간:  30분
힌트 참조 유무: 무

https://www.acmicpc.net/problem/10026

1 번째 시도   

• 할 일 
  • 배열 초기화
  • 적록색맹x 일때 dfs
  • 적록색맹o 일때 dfs
• 인접해있는 요소를 비교하는 문제일 때는 방향 설정 배열을 쓰는 것이 Point!

  •  static int[] x = {1,0,0,-1};
     static int[] y = {0,1,-1,0};

    
    
• dfs함수의 for문과 main함수에서 for문을 짤 때 헷갈릴 수도 있다.
  • dfs함수는 동,서,남,북 방향으로 주어진 글자랑 같은 게 무엇인지 찾는 것이고 
  • main함수의 for문은 전체배열을 순서대로 순회하는 것이다 
• 문제가 카드의 경우의 수를 구하는 경우라면 main함수의 for문은 없을 것이다. dfs 함수내에만 존재할 것이다.
  • dfs함수에서 전체 배열을 순서대로 순회하기 때문에 main함수에서 전체배열을 순서대로 순회할 필요가 없기 때문에.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

    static int[] x = {1, 0, 0, -1};
    static int[] y = {0, 1, -1, 0};

    static String[][] arr;
    static int yesRGB;
    static int noRGB;
    static boolean[][] visited;
    static boolean[][] visited2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //visted1,2 초기화
        visited = new boolean[N][N];
        visited2 = new boolean[N][N];

        //배열 초기화
        arr = new String[N][N];
        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                arr[i][j] = s[j];
            }
        }

        //적록색맹 아닐 때 dfs
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    dfsA(i, j, arr[i][j]);
                    yesRGB++;
                }
            }
        }

        //적록색맹일 때 dfs
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited2[i][j]) {
                    dfsB(i, j, arr[i][j]);
                    noRGB++;
                }
            }
        }

        System.out.println(yesRGB+ " " + noRGB);
    }

    private static void dfsA(int i, int j, String s) {
        visited[i][j] = true;

        for (int k = 0; k < 4; k++) {
            int nextx = j + x[k];
            int nexty = i + y[k];
            if (nexty >= 0 && nexty < arr.length && nextx >= 0 && nextx < arr.length) {
                if (!visited[nexty][nextx] && s.equals(arr[nexty][nextx])) {
                    dfsA(nexty, nextx, arr[nexty][nextx]);
                }
            }
        }
    }

    private static void dfsB(int i, int j, String s) {
        visited2[i][j] = true;

        for (int k = 0; k < 4; k++) {
            int nextx = j + x[k];
            int nexty = i + y[k];
            if (nexty >= 0 && nexty < arr.length && nextx >= 0 && nextx < arr.length) {
                if (!visited2[nexty][nextx]) {
                    if(s.equals("R") || s.equals("G")) {
                        if(arr[nexty][nextx].equals("R") || arr[nexty][nextx].equals("G")) {
                            dfsB(nexty, nextx, arr[nexty][nextx]);
                        }
                    }
                    else {
                        if(s.equals(arr[nexty][nextx])) {
                            dfsB(nexty, nextx, arr[nexty][nextx]);
                        }
                    }
                }
            }
        }
    }
}

 

다른 사람 코드  

 

다른 사람은 나와 같이 두 개의 dfs를 만들지 않고  R을 G로 바꾼 배열 하나, 정상적인 배열 하나를 만들어 dfs 하나로 사용했다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Main {

    static int N;
    static char[][] normalMap;
    static char[][] abnormalMap;
    static int normal;
    static int abnormal;

    static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("적록색약_10026.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        normalMap = new char[N][N];
        abnormalMap = new char[N][N];
        String line;
        for (int i = 0; i < N; ++i) {
            line = br.readLine();
            for (int j = 0; j < N; ++j) {
                normalMap[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (normalMap[i][j] == 'R') {
                    abnormalMap[i][j] = 'G';
                } else
                    abnormalMap[i][j] = normalMap[i][j];
            }
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (normalMap[i][j] != 'X') {
                    dfs(i, j, normalMap);
                    ++normal;
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (abnormalMap[i][j] != 'X') {
                    dfs(i, j, abnormalMap);
                    ++abnormal;
                }
            }
        }

        System.out.print(normal + " " + abnormal);
    }

    private static void dfs(int r, int c, char[][] map) {
        char now = map[r][c];
        map[r][c] = 'X';

        for (int i = 0; i < 4; ++i) {
            int nr = r + delta[i][0];
            int nc = c + delta[i][1];
            if (nr < 0 || nr > N - 1 || nc < 0 || nc > N - 1 || map[nr][nc] == 'X' || now != map[nr][nc]) {
                continue;
            }
            dfs(nr, nc, map);
        }
    }

}