BOJ_10226 / 적록색약

차_현·2024년 10월 10일
boj코딩테스트
2

📌 문제 탐색하기

  • 입력:
    • 첫째 줄
      • N : 크기가 N X N의 그리드
      • 그리고 해당 크기의 그리드에 각 칸이 주어진다.
    • 둘째줄 부터
      • 그리드의 각 칸에 R, G ,B 의 값이 들어간다.
      • 값이 비어있는 경우는 없는 것 같으니, 나중에 코드를 짤 때 값이 있고 없고 여부의 체크는 하지 않아도 될지도?
  • 출력
    • 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수 출력

📌 어떤 알고리즘?

  • 그래프 탐색 알고리즘
    • 적록색약이 아닌 사람
      • 지금 내가 위치한 칸과 이 칸의 상하좌우로 연결된 칸들의 색깔이 같으면 같은 구역
    • 적록색약인 사람
      • 지금 내가 위치한 칸과 이 칸의 상하좌우로 연결된 칸들의 색깔이 같으면 같은 구역
      • 지금 내가 위치한 칸과 이 칸의 상하좌우로 연결된 칸들의 색깔중 빨간색과 초록색은 같은 색으로 구분하여 같은 구역으로 인지한다.
    • 내가 지금 위치한 칸들의 주위 칸들을 비교해보고 조건에 일치하면 또 그 칸에서 계속 비교해야 하기 때문에 그래프 탐색 알고리즘을 선택하기로 하였고, 이 중에서 BFS는 시작한 노드로부터 연결된 모든 인접 노드를 한 번에 탐색하여 "구역"을 구성하는 데 유리하기 때문에, 같은 구역 내에서 동일한 색상을 가진 노드들을 효과적으로 찾아낼 수 있다.

📌 코드 설계하기

  1. Input 받기 & 값 초기화
   			N = Integer.parseInt(bf.readLine());
        color = new String[N][N];

        //색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            color[i] = bf.readLine().split("");
        }
  • 그냥 단순하게 값을 입력받으면 된다.
  1. DFS를 이용한 섬 탐색
  • 각 칸을 탐색하면서, 방문하지 않았고 땅(1)이면 DFS를 시작합니다.
    public static int howManyIsLands(int[][] map, boolean[][] visited) {
        int count = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    dfs(map, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }
  • DFS는 해당 칸과 연결된 모든 땅을 방문 처리하며, 섬의 개수를 count합니다.
    public static void dfs(int[][] map, boolean[][] visited, int i, int j) {
        stack.push(new int[]{i, j});
        visited[i][j] = true;

        while (!stack.isEmpty()) {
            int[] current = stack.pop(); // {0, 0}
            int dx = current[0];
            int dy = current[1];

            for (int k = 0; k < dX.length; k++) {
                int x = dx + dX[k];
                int y = dy + dY[k];

                if (x >= 0 && y >= 0 && x < h && y < w && map[x][y] == 1 && !visited[x][y]) {
                    stack.push(new int[]{x, y});
                    visited[x][y] = true;
                }
            }

        }
    }

📌 시도 회차 수정 사항 (리팩토링 전 / 후)

  • 배열 초기화에 있어서..

    • 처음에 그냥 색깔 배열을 2차원으로 초기화해서 사용하면 되기 때문에 정말 단순하게 아래와 같이 코드를 짰다.

         		  //색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            char[] charArray = bf.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                color[i][j] = String.valueOf(charArray[j]);
            }
        }

    • 그런데 뭔가 너무 불필요한 코드들이 많은 것 같기도 하고 굳이 2중 for문을 쓸 필요가 없는데, 너무 무지성으로 빨리 한 느낌..?

    • 그래서 리팩토링 할 때 배열 초기화 코드를 아래와 같이 바꿨다.

              //색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            color[i] = bf.readLine().split("");
        }

    • 훨씬 코드가 간단해졌고, 머리속으로는 아는 코드이지만 이걸 빨리 구현하려는 생각 때문에 너무 직관적으로 돌아간 것 같다. 해당 방식을 조금 잘 기억해보자..앞으로…초기화할 때

  • 그리고 처음에는 적록색약이 아닌 사람과 적록색약인 사람의 메소드를 분리하였었다.
    이렇게 분리에 포커스를 맞춰서 구현하다보니 BFS 메소드 조차 분리하여 코드의 양이 길어지는 단점이 발생하였다.


package BOJ_10026;

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

public class BOJ_10026 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static String[][] color;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();

    static int[] dX = new int[]{0, 0, 1, -1};
    static int[] dY = new int[]{1, -1, 0, 0};

    public static void main(String[] args) throws IOException{
        N = Integer.parseInt(bf.readLine());
        color = new String[N][N];

        //색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            color[i] = bf.readLine().split("");
        }

        int countNormal = checkNormal();
        int countAbnormal = checkAbNormal();
        System.out.println(countNormal + " " + countAbnormal);
    }

    public static int checkNormal() {
        int count = 0;
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs_Normal(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public static int checkAbNormal() {
        int count = 0;
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs_Abnormal(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public static void bfs_Normal(int x, int y) {
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int dx = current[0];
            int dy = current[1];

            for (int k = 0; k < dX.length; k++) {
                int a = dx + dX[k];
                int b = dy + dY[k];

                if (a >= 0 && b >= 0 && a < N && b < N && !visited[a][b] && color[a][b].equals(color[x][y])) {
                    queue.add(new int[]{a, b});
                    visited[a][b] = true;
                }
            }
        }
    }

    public static void bfs_Abnormal(int x, int y) {
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int dx = current[0];
            int dy = current[1];

            for (int k = 0; k < dX.length; k++) {
                int a = dx + dX[k];
                int b = dy + dY[k];

                if (a >= 0 && b >= 0 && a < N && b < N && !visited[a][b]) {
                    if (color[a][b].equals(color[x][y]) || validColor(color[x][y], color[a][b])) {
                        queue.add(new int[]{a, b});
                        visited[a][b] = true;
                    }
                }
            }
        }
    }

    public static boolean validColor(String startColor, String comparedColor) {
        if (startColor.equals("R") && comparedColor.equals("G")) {
            return true;
        } else if (startColor.equals("G") && comparedColor.equals("R")) {
            return true;
        } else return false;
    }
}
  • 분리하지 않고 Flag형식으로 적록색약이 아닌 사람과 적록색약인 사람을 구분하는 방식 → 리팩토링 후
  • 이후, 위의 방식은 확실하게 분리되어 있는 장점이 있지만 불필요한 메소드들과 코드의 양 증대로 생산성이 떨어질 수 있다는 느낌이 들었다. 그래서 이전 코드 정답 확인 후, 위 코드를 리팩토링 해보기로 했다.
public class BOJ_10026 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static String[][] color;
    static boolean[][] visited;
    static final int[] dX = {0, 0, 1, -1};
    static final int[] dY = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(bf.readLine());
        color = new String[N][N];

        // 색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            color[i] = bf.readLine().split("");
        }

        int countNormal = countRegions(false);
        int countAbnormal = countRegions(true);
        System.out.println(countNormal + " " + countAbnormal);
    }

    public static int countRegions(boolean isColorBlind) {
        int count = 0;
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, isColorBlind);
                    count++;
                }
            }
        }
        return count;
    }

    public static void bfs(int x, int y, boolean isColorBlind) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        String startColor = color[x][y];

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int a = current[0];
            int b = current[1];

            for (int k = 0; k < dX.length; k++) {
                int dx = a + dX[k];
                int dy = b + dY[k];

                if (dx >= 0 && dy >= 0 && dx < N && dy < N && !visited[dx][dy]) {
                    if (isSameColor(startColor, color[dx][dy], isColorBlind)) {
                        queue.add(new int[]{dx, dy});
                        visited[dx][dy] = true;
                    }
                }
            }
        }
    }

    public static boolean isSameColor(String color1, String color2, boolean isColorBlind) {
        if (isColorBlind && (color1.equals("R") || color1.equals("G"))) {
            return color2.equals("R") || color2.equals("G");
        }
        return color1.equals(color2);
    }
}
  • 불필요한 메소드의 중복이 사라지고 countRegions(false) / countRegions(true) 처럼 같은 메소드를 사용하고, isColorBlind의 Flag 변수를 사용하여 적록색약이 아닌 사람과 적록색약인 사람을 구분하였다.

📌 정답 코드

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

public class BOJ_10026 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static String[][] color;
    static boolean[][] visited;
    static final int[] dX = {0, 0, 1, -1};
    static final int[] dY = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(bf.readLine());
        color = new String[N][N];

        // 색깔 2차원 배열 초기화
        for (int i = 0; i < N; i++) {
            color[i] = bf.readLine().split("");
        }

        int countNormal = countRegions(false);
        int countAbnormal = countRegions(true);
        System.out.println(countNormal + " " + countAbnormal);
    }

    public static int countRegions(boolean isColorBlind) {
        int count = 0;
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, isColorBlind);
                    count++;
                }
            }
        }
        return count;
    }

    public static void bfs(int x, int y, boolean isColorBlind) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        String startColor = color[x][y];

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int a = current[0];
            int b = current[1];

            for (int k = 0; k < dX.length; k++) {
                int dx = a + dX[k];
                int dy = b + dY[k];

                if (dx >= 0 && dy >= 0 && dx < N && dy < N && !visited[dx][dy]) {
                    if (isSameColor(startColor, color[dx][dy], isColorBlind)) {
                        queue.add(new int[]{dx, dy});
                        visited[dx][dy] = true;
                    }
                }
            }
        }
    }

    public static boolean isSameColor(String color1, String color2, boolean isColorBlind) {
        if (isColorBlind && (color1.equals("R") || color1.equals("G"))) {
            return color2.equals("R") || color2.equals("G");
        }
        return color1.equals(color2);
    }
}

📌 시간 복잡도?

  • 주요 함수
  1. main(): 색상을 입력받아 배열을 초기화하고, 적록색약 여부에 따라 countRegions() 함수를 호출
  2. countRegions(boolean isColorBlind): 모든 셀을 순회하며, 방문하지 않은 셀에 대해 BFS 탐색을 수행하여 하나의 구역을 찾고, 구역의 개수를 증가시킴
  3. bfs(int x, int y, boolean isColorBlind): BFS를 사용하여 시작 셀로부터 같은 구역에 포함되는 모든 셀을 방문합니다. 각 인접 셀에 대해 isSameColor() 함수를 호출하여 같은 색상인지 확인함
  4. isSameColor(String color1, String color2, boolean isColorBlind): 적록색약 여부에 따라 두 색상이 같은 색상으로 취급되는지 판단
  • 시간 복잡도 분석

1. countRegions() 함수의 시간 복잡도:

  • countRegions() 함수는 배열의 모든 셀에 대해 방문 여부를 검
    N x N 크기의 배열을 완전히 순회하므로 기본적으로 O(N^2) 시간이 걸림
  • 각 셀에 대해 BFS 탐색이 수행되며, 각 BFS 호출 시 최대 N^2 번의 탐색이 가능함

2. bfs() 함수의 시간 복잡도:

  • BFS는 그래프에서 각 노드를 한 번만 방문하고, 해당 노드의 인접 노드를 탐색하므로 O(V + E) 시간 복잡도를 가짐
  • 여기서 V는 셀의 수(N^2), E는 인접 셀의 수(최대 4N^2)
  • 따라서, BFS의 최악 시간 복잡도는 O(N^2)

3. 전체 시간 복잡도:

  • countRegions() 함수는 BFS 탐색을 여러 번 호출하며, 각 BFS 호출에서 최대 N^2 셀을 탐색할 수 있습니다.
  • 전체적으로 countRegions()는 배열의 각 셀을 한 번만 탐색하므로, 각 호출의 시간 복잡도는 O(N^2)
  • 이 함수는 적록색약 여부에 대해 한 번씩 호출되므로 총 시간 복잡도는 2 * O(N^2), 즉 O(N^2)

4. 결론

이 코드의 전체 시간 복잡도는 O(N^2)
N의 값이 커져도 N^2의 크기에 비례하여 수행 시간은 선형적으로 증가함
N이 최대 100이므로 최악의 경우에도 10000 번의 연산으로 충분히 처리할 수 있음

profile
차_현
이전 포스트

BOJ_4963 / 섬의 갯수

다음 포스트

ServiceImpl 쓰지말라고요?

1개의 댓글

comment-user-thumbnail
호이초이
2024년 10월 11일

나야 들기름

답글 달기