백준 JAVA 10026번 적록색약 리뷰

 

블로그 이전, 2023. 6. 23. 19:25 에 작성했던 글입니다.

10026번: 적록색약

접근방법

dfs 문제라고 생각은 했다. 그렇다고 풀지는 못했다... 

다른 블로그를 참고하며 풀었다.

 

모든 노드를 방문하는 것이 주요한 문제이고 경로의 특징을 저장해야하는 문제라고 생각해서 dfs라고 접근했다. 

DFS 풀이 방법

1.최상단 노드 확인 후 스택에 넣기

2.최상단 노드와 인접하고 방문하지 않은 노드를 스택에 넣는다, 그리고 방문처리를 한다.

만약 방문하지 않은 인접노드가 없을 경우 최상단 노드를 스택에서 뺀다.

1,2번을 계속 반복한다.

DFS는 스택을 이용하는데 스택을 만들 필요없이 재귀함수를 이용하면 된다. 

 

코드 설명

1.정상/비정상 두 가지 경우로 나누어서 dfs를 호출한다.

2.정상 dfs를 다한 후 비정상 dfs를 구할 때는 visited를 초기화한다. 정상 dfs에서 썼으니까

3.비정상 dfs를 위해 초기화한 배열에서 G를 R로 바꿨다.

4.0과 1로 이루어진 2차원 배열 dfs를 풀 때는 1을 기준으로 문제를 풀었지만 R,G,B 세가지로 나누어 구역을 세는 것이기 때문에 R,G,B를 명시하며 찾지 않았다. if (!visited[i][j]) { 라든지, tmpchar을 이용해 구하는 모습을 볼 수 있었다.

 

나의 풀이

import java.io.*;

public class Main{
    static int[] dirX ={0,0,1,-1};
    static int[] dirY = {1,-1,0,0};
    static int N, nowx,nowy;
    static boolean[][] visited;
    static  char[][] art;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        art = new char[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                art[i][j]=str.charAt(j);
            }
        }

        //정상일때
        int cnt=0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        int normal = cnt;


        //비정상일때
        visited = new boolean[N][N]; //배열 초기화
        cnt=0;
        for(int i=0; i<N; i++) {
            for (int j = 0; j < N; j++) {
                if (art[i][j] == 'G') {
                    art[i][j] = 'R';

                }
            }
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        int abnormal =cnt;
        System.out.println(normal+" "+abnormal);

    }
    public static void dfs(int x, int y){
        visited[x][y]=true;
        int tmpchar = art[x][y];

        for(int i=0; i<4; i++){ //방문하지 않은 인접노드 찾는 중
            nowx = x+dirX[i];
            nowy = y+dirY[i];

            if(nowx>=0&&nowy>=0&&nowx<N&&nowy<N){
                if(art[nowx][nowy]==tmpchar&&visited[nowx][nowy]==false){
                    visited[nowx][nowy]=true;
                    dfs(nowx,nowy);
                }
            }
        }
    }
}