[BOJ] 10026. 적록색약 - JAVA 자바

10026번: 적록색약

• 92ms
• DFS BFS

적록색약일 경우의 나눠지는 구역과 적록색약이 아닐 경우 나눠지는 구역의 수를 세는 문제이다.

 

입력값을 저장할 이차원 배열을 두 개 선언하여 적록색약이 아닌 경우 입력값을 그대로 저장하고 적록색약인 경우에는 'G'값을 'R'값으로 저장하였다. 이중 for문을 돌며 적록색약이 아닌 경우의 dfs, 적록색약인 경우의 dfs 탐색을 통해 주변의 같은 색 좌표들을 모두 방문처리하여 구역을 카운팅하는 방식으로 구현하였다.

 

좌표의 상하좌우를 탐색하고 구역을 구분하는 문제로 DFS / BFS로 쉽게 해결할 수 있다.

DFS로 구현

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

// DFS로 해결
// 84ms
public class Main {
    static int N;
    static char[][] board, board2;
    static boolean[][] visited, visited2;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    public static boolean Valid(int x, int y) {
        if (x >= 0 && x < N && y >= 0 && y < N)
            return true;
        return false;
    }

    public static void dfs(int x, int y, char c, char[][] board, boolean[][] visited) {
        // 상하좌우로 같은 색이 있는지 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (Valid(nx, ny) && !visited[nx][ny] && board[nx][ny] == c) {
                // 같은 색이라면 방문표시
                visited[nx][ny] = true;
                dfs(nx, ny, c, board, visited);
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        board2 = new char[N][N];
        visited = new boolean[N][N];
        visited2 = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                char c = str.charAt(j);
                board[i][j] = c;
                board2[i][j] = (c == 'G') ? 'R' : c;
            }
        }
        int count = 0, count2 = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 방문하지 않은 곳 탐색
                if (!visited[i][j]) {
                    dfs(i, j, board[i][j], board, visited);
                    count++;
                }
                if (!visited2[i][j]) {
                    dfs(i, j, board2[i][j], board2, visited2);
                    count2++;
                }
            }
        }
        System.out.println(count + " " + count2);
    }
}

BFS로 구현

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

// BFS 해결
// 92ms
public class Main2 {
    static int N;
    static char[][] board, board2;
    static boolean[][] visited, visited2;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    public static boolean Valid(int x, int y) {
        if (x >= 0 && x < N && y >= 0 && y < N)
            return true;
        return false;
    }

    public static void bfs(int x, int y, char c, char[][] board, boolean[][] visited) {
        // 상하좌우로 같은 색이 있는지 탐색
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.offer(new int[] { x, y });
        while (!q.isEmpty()) {
            int[] now = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if (Valid(nx, ny) && !visited[nx][ny] && board[nx][ny] == c) {
                    // 같은 색이라면 방문표시
                    visited[nx][ny] = true;
                    q.offer(new int[] { nx, ny });
                }
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        board2 = new char[N][N];
        visited = new boolean[N][N];
        visited2 = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                char c = str.charAt(j);
                board[i][j] = c;
                board2[i][j] = (c == 'G') ? 'R' : c;
            }
        }
        int count = 0, count2 = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 방문하지 않은 곳 탐색
                if (!visited[i][j]) {
                    bfs(i, j, board[i][j], board, visited);
                    count++;
                }
                if (!visited2[i][j]) {
                    bfs(i, j, board2[i][j], board2, visited2);
                    count2++;
                }
            }
        }
        System.out.println(count + " " + count2);
    }
}