[백준/1012/유기농 배추]

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

1012번: 유기농 배추

<<풀이>>

 

우선 이 문제는 DFS로 풀어야 한다는 생각이 들었다. 그래서 이차원 배열을 활용해서 

 

DFS형태로 구상을 했다.

 

만약 해당 배열에 값이 1이라면 dx, dy로 상하 좌우에 1인지 아닌지 최종적으로 없을 때 까지 깊게 들어간다.

 

그리고 이미 들어간 값은 ch에 같은 좌표에 1을 추가함으로써 중복계산 되는 것을 막으려 했다.

 

논리적으로는 틀린게 없어보이지만..

 

틀렸다 ㅠ

 

왤까?

import java.util.Scanner;

class Main {

        public static int[][] ch;
        public static int count;
        public static int[] dx = {-1, 1, 0, 0};
        public static int[] dy = {0, 0, -1, 1};


        private void DFS(int n, int m, int[][] arr, int N, int M) {
                if (N >= 0 && N < n && M >= 0 && M < m && arr[N][M] == 1 && ch[N][M] != 1) {
                        ch[N][M] = 1;
                        DFS(n, m, arr, n+dx[0], m+dy[0]);
                        DFS(n, m, arr, n+dx[1], m+dy[1]);
                        DFS(n, m, arr, n+dx[2], m+dy[2]);
                        DFS(n, m, arr, n+dx[3], m+dy[3]);
                } else return;
        }

        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int test = in.nextInt();


                for (int i = 0; i < test; i++) {
                        int m = in.nextInt();
                        int n = in.nextInt();
                        int where = in.nextInt();
                        int[][] arr = new int[n][m];
                         ch = new int[n][m];

                        for (int j = 0; j < where; j++) {
                                int b = in.nextInt();
                                int a = in.nextInt();

                               arr[a][b] = 1;
                        }

                        for (int j = 0; j < n; j++) {
                                for (int k = 0; k < m; k++) {
                                        if (arr[j][k] == 1 && ch[j][k] != 1) {
                                                ch[j][k] = 1;
                                                T.DFS(n, m, arr, j+dx[0], k+dy[0]);
                                                T.DFS(n, m, arr, j+dx[1], k+dy[1]);
                                                T.DFS(n, m, arr, j+dx[2], k+dy[2]);
                                                T.DFS(n, m, arr, j+dx[3], k+dy[3]);
                                                count++;
                                        }
                                }
                        }
                        System.out.println(count);

                        ch = new int[n][m];
                        count = 0;
                }
        }
}

 

ㅋㅋ 알고보니까 값을 잘못 대입했다 ㅎㅎ..

 

 

위 아래 코드를 잘 보면 N이 들어갈 자리를 n으로 하고 M은 m을 넣은 셈이다.

 

코딩이 길어지고 루즈해지다 보니까 헷갈렸나보다 !!

 

이래서 코딩을 할 때 이름 선정도 중요한 문제인 것이다.

 

작성할 때 귀찮더라도 제대로 작성하고 헷갈리지 않게 해야겠다.

 

바꾸니 바로 정답이다 ~!

import java.util.ArrayList;
import java.util.Scanner;

class Main {

        public static int[][] ch;
        public static int count;
        public static int[] dx = {-1, 1, 0, 0};
        public static int[] dy = {0, 0, -1, 1};


        private void DFS(int n, int m, int[][] arr, int N, int M) {
                if (N >= 0 && N < n && M >= 0 && M < m && arr[N][M] == 1 && ch[N][M] != 1) {
                        ch[N][M] = 1;
                        DFS(n, m, arr, N+dx[0], M+dy[0]);
                        DFS(n, m, arr, N+dx[1], M+dy[1]);
                        DFS(n, m, arr, N+dx[2], M+dy[2]);
                        DFS(n, m, arr, N+dx[3], M+dy[3]);
                } else return;
        }

        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int test = in.nextInt();
                ArrayList<Integer> answer = new ArrayList<>();


                for (int i = 0; i < test; i++) {
                        int m = in.nextInt();
                        int n = in.nextInt();
                        int where = in.nextInt();
                        int[][] arr = new int[n][m];
                         ch = new int[n][m];

                        for (int j = 0; j < where; j++) {
                                int b = in.nextInt();
                                int a = in.nextInt();

                               arr[a][b] = 1;
                        }

                        for (int j = 0; j < n; j++) {
                                for (int k = 0; k < m; k++) {
                                        if (arr[j][k] == 1 && ch[j][k] != 1) {
                                                ch[j][k] = 1;
                                                T.DFS(n, m, arr, j+dx[0], k+dy[0]);
                                                T.DFS(n, m, arr, j+dx[1], k+dy[1]);
                                                T.DFS(n, m, arr, j+dx[2], k+dy[2]);
                                                T.DFS(n, m, arr, j+dx[3], k+dy[3]);
                                                count++;
                                        }
                                }
                        }

                        answer.add(count);

                        ch = new int[n][m];
                        count = 0;
                }

                for(int x : answer) System.out.println(x);
        }
}

 

아래 방식으로 코드를 짜도 정답이다.

생각해보면 저렇게 처음에 시작해도 문제가 없다.

시작점이 다른 것 뿐이다.

 

아직 익숙하지 않으니 코드가 복잡해지고 쓸데 없이 길어지는 상황인 것이다.

 

꾸준히 연습해서 이러한 부분 또한 보완해 나가자 !!

import java.util.ArrayList;
import java.util.Scanner;

class Main {

        public static int[][] ch;
        public static int count;
        public static int[] dx = {-1, 1, 0, 0};
        public static int[] dy = {0, 0, -1, 1};


        private void DFS(int n, int m, int[][] arr, int N, int M) {
                if (N >= 0 && N < n && M >= 0 && M < m && arr[N][M] == 1 && ch[N][M] != 1) {
                        ch[N][M] = 1;
                        DFS(n, m, arr, N+dx[0], M+dy[0]);
                        DFS(n, m, arr, N+dx[1], M+dy[1]);
                        DFS(n, m, arr, N+dx[2], M+dy[2]);
                        DFS(n, m, arr, N+dx[3], M+dy[3]);
                } else return;
        }

        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int test = in.nextInt();
                ArrayList<Integer> answer = new ArrayList<>();


                for (int i = 0; i < test; i++) {
                        int m = in.nextInt();
                        int n = in.nextInt();
                        int where = in.nextInt();
                        int[][] arr = new int[n][m];
                         ch = new int[n][m];

                        for (int j = 0; j < where; j++) {
                                int b = in.nextInt();
                                int a = in.nextInt();

                               arr[a][b] = 1;
                        }

                        for (int j = 0; j < n; j++) {
                                for (int k = 0; k < m; k++) {
                                        if (arr[j][k] == 1 && ch[j][k] != 1) {
                                                T.DFS(n, m, arr, j, k);
                                                count++;
                                        }

                                }
                        }

                        answer.add(count);

                        ch = new int[n][m];
                        count = 0;
                }

                for(int x : answer) System.out.println(x);
        }
}

 

이 문제를 통해서 dx, dy를 활용해보았고, DFS에 대해 공부하는 좋은 계기가 되었다.

 

아직은 익숙하지 않은 DFS BFS 익숙해질 수 있도록 계속 연습하자.