[백준문제풀이] 10026 적록색약 java

dfs bfs문제는 계속 헷갈려~~

 

접근법 : 

**1) 어떻게 풀 것인가?**

dfs로 풀어도 ㄱㅊ고 bfs로 풀어도 괜찮은 문제인것같다. 

일단 난 dfs로 풀었다. 

풀이과정은 아래와 같다. 

예제 값을 주었을 때 비적록색약인이 본 구역은 4가지로 나뉜다.

 

반면 적록색약인이 보기엔 3구역으로 나뉜다. 

 

핵심적으로 필요한 것 

1. 방문을 확인하는 boolean [][] check;

2. 특정좌표를 방문했을때, 해당 좌표의 위 부터 반시계방향으로 갈 좌표값을 알려주는 int[] mx, int[]my

 

핵심 dfs 내용

( 비 적록색약인)

1. 기준좌표에서 시작하여 시계 방향으로 좌표를 순회한다. (초반엔 0,0) 기준좌표는 방문했다는 표시를한다.

2. 방문한 좌표값이 기준좌표와 값이 같고, 아직 방문한 적 없다면 해당 좌표를 기준좌표로 잡고 1부터 다시 과정을 반복한다.

3. 주위 모든 좌표가 위 조건을 만족하지 않을때 이전 기준좌표로 돌아가 중단 되었던 시계순회를 끝까지 한다.

4. 기존에 불러왔던 재귀가 끝날때까지한다.

5. main함수로 돌아가면 한 구역이 끝났단 뜻이므로 count를 더해주고, 방문하지 않은 좌표부터 dfs를 시작한다.

 

핵심 dfs 내용

( 적록색약인)

위 과정의 2에 약간의 조건을 추가해준다.

만약 기준좌표값이 R 혹은 G 이며 방문좌표값도 R 혹은 G 라면 같다고 취급한다.

 

**2) 시간복잡도**

1초다. 1억개의 데이터를 계산 가능하다. 1<= n <= 100이라서 최대 10000까지 인것같다......

인접리스트로 진행했으므로 시간복잡도는 O(V+E) 가 된다. 

V : 100 * 100 = 10^4

E : 한 좌표당 최대 4개까지 인접해있을 수 있다. 4V

O(V+E) = O(5V) = 5 * 10^4

최종 시간복잡도 : 2* 5* 10^4 = 10^5

 

**3) 공간복잡도**

128mb

 

**4) 풀면서 놓쳤던점**

 두 방법을 생각하고 풀었다면 좋았을텐데 dfs 방법밖에 생각 안 났음

 

**5) 이 문제를 통해 얻어갈 것**

사실 이 문제는 다른 두 문제를 풀다가 내가 너무 못 풀길래..... 좀 단계를 내려와서 푼 문제다.

인접행렬과 인접리스트에 따라 따로 시간복잡도가 존재한다는것도 처음 알았다. 

난 항상 한가지로만 풀어서,, 공부를 더 열심히해야겠다 흑

import java.io.*;

public class Main {
    static char[][] maps;
    static boolean[][] check;
    static StringBuilder sb;
    static int n;
    static int[] mx = {-1,0,1,0};
    static int[] my = {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        maps = new char[n][n];
        check = new boolean[n][n];
        int count =0;
        for(int i=0 ;i<n;i++){
            String strings = br.readLine();
            for(int j=0; j<n;j++){
                maps[i][j] = strings.charAt(j);
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!check[i][j]){
                    colorDFS(i,j);
                    count++;
                }
            }
        }
        sb.append(count+" ");
        count = 0;
        check = new boolean[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!check[i][j]){
                    colorBlinds(i,j);
                    count++;
                }
            }
        }
        sb.append(count+" ");
        System.out.println(sb);
    }

    static void colorDFS(int x,int y){
            check[x][y] = true;
            for(int i=0; i<4;i++){
                int newx = x+mx[i];
                int newy = y+my[i];
                if(newx>=n || newx <0 || newy >=n || newy<0);
                else{
                        if(maps[newx][newy] == maps[x][y] && !check[newx][newy]){
                            colorDFS(newx,newy);
                        }
                }
            }
        }

    static void colorBlinds(int x,int y){
        check[x][y] = true;
        char c = maps[x][y];
        for(int i=0; i<4;i++){
            int newx = x+mx[i];
            int newy = y+my[i];
            if(newx>=n || newx <0 || newy >=n || newy<0);
            else{
                if(c == 'R' || c == 'G'){
                    if(maps[newx][newy] == 'R' || maps[newx][newy] == 'G'){
                        if(!check[newx][newy]){
                            colorBlinds(newx,newy);
                        }
                    }
                }
                else if(maps[newx][newy] == c&& !check[newx][newy]){
                    colorBlinds(newx,newy);
                }
            }
        }
    }


}