(#1012 Java) 유기농 배추

 

 

문제 해결

 

dfs 문제로 풀 수 있는 문제이다.

static으로 main 밖에서 선언할 것들을 선언해준다.

static int T;
static int M,N,K;
static int[][] Graph;
static boolean[][] Visited; //방문 여부
static int count;
static int[] dx = {0, -1, 0, 1}; //좌우
static int[] dy = {-1, 0, 1, 0}; //상하

 

 

dfs 함수를 만들어준다.

배추흰지렁이는 상하좌우로 모두 움직일 수 있으므로 반복문의 범위를 4번 반복하도록 설정해준다.

각각 행/열의 새로운 좌표를 만들어준 후, 새로운 좌표의 범위 체크, 방문여부 체크, 1인지 아닌지 체크 (배추가 위치해있는 곳)를 한 후 모든 검증이 끝나면 적절한 좌표들을 dfs 함수로 넣어 호출해준다.

 

static void dfs(int x, int y) {
    Visited[x][y] = true;

    for(int i = 0; i < 4; i++) { //상하좌우 4번
        int nr = x + dx[i]; //새로운 행 좌표
        int nc = y + dy[i]; //새로운 열 좌표

        if(nr < 0 || nr > M-1 || nc < 0 || nc > N-1) //범위 벗어나면 continue
            continue;
        if(Visited[nr][nc]) //방문했으면 continue
            continue;
        if(Graph[nr][nc] != 1) //1이 아니면 continue
            continue;

        dfs(nr,nc);
    }
}

 

 

main 함수를 보자. 우선 테스트 케이스의 수 T를 입력받고, T만큼 M,N,K를 입력 받는다. 이 때 M,N을 입력받은 후 Gragh와 Visited 배열의 크기를 선언해준다.

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    T = in.nextInt();

    for(int i = 0; i < T; i++) { //테스트 케이스만큼 반복

        count = 0;

        M = in.nextInt();
        N = in.nextInt();
        K = in.nextInt();

        //M,N 입력받은 후 배열 크기 선언
        Graph = new int[M][N];
        Visited = new boolean[M][N];

 

 

테스트 케이스 T만큼 반복할 반목문 안에 포함될 반복문들이다.

 

우선 K줄에 배추의 위치가 주어진다고 했으므로, cx,cy를 각각 입력받은 후 두 개씩 짝지어 1이라고 세팅해둔다. (x, y좌표 2개의 숫자가 한 쌍이므로)

 

그리고 각각 행/열에 대한 이중루프를 돌며 Graph가 1로 세팅되어 있고 (유기농 배추가 있는 곳), 아직 방문하지 않은 곳이라면, dfs함수를 호출해주고 count를 증가시켜준다. 

for (int j = 0; j < K; j++) {
    int cx = in.nextInt();
    int cy = in.nextInt();

    Graph[cx][cy] = 1; //테스트 케이스만큼 두 개씩 입력 받아 배열을 1로 세팅
}

for(int x = 0; x < M; x++) {
    for(int y = 0; y < N; y++) {
        if (Graph[x][y] == 1 && !Visited[x][y]) {
            dfs(x,y);
            count++;
        }
    }
}

 

 

그리고 count를 출력해주면 끝!! 

 

항상 주의해야할 점과 내가 자주 놓치는 부분은 각 테스트 케이스마다 count를 0으로, Graph 배열, Visited 배열을 초기화시켜주는 것이다. 이를 초기화시켜주는 위치에 조금 더 신경써주자!!

 

최종 코드

 

package org.example.DfsBfs;

import java.util.Scanner;

public class OrganicCabbage {
    static int T;
    static int M,N,K;
    static int[][] Graph;
    static boolean[][] Visited; //방문 여부
    static int count;
    static int[] dx = {0, -1, 0, 1}; //좌우
    static int[] dy = {-1, 0, 1, 0}; //상하

    static void dfs(int x, int y) {
        Visited[x][y] = true;

        for(int i = 0; i < 4; i++) { //상하좌우 4번
            int nr = x + dx[i]; //새로운 행 좌표
            int nc = y + dy[i]; //새로운 열 좌표

            if(nr < 0 || nr > M-1 || nc < 0 || nc > N-1) //범위 벗어나면 continue
                continue;
            if(Visited[nr][nc]) //방문했으면 continue
                continue;
            if(Graph[nr][nc] != 1) //1이 아니면 continue
                continue;

            dfs(nr,nc);
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        T = in.nextInt();

        for(int i = 0; i < T; i++) { //테스트 케이스만큼 반복

            count = 0;

            M = in.nextInt();
            N = in.nextInt();
            K = in.nextInt();

            //M,N 입력받은 후 배열 크기 선언
            Graph = new int[M][N];
            Visited = new boolean[M][N];

            for (int j = 0; j < K; j++) {
                int cx = in.nextInt();
                int cy = in.nextInt();

                Graph[cx][cy] = 1; //테스트 케이스만큼 두 개씩 입력 받아 배열을 1로 세팅
            }

            for(int x = 0; x < M; x++) {
                for(int y = 0; y < N; y++) {
                    if (Graph[x][y] == 1 && !Visited[x][y]) {
                        dfs(x,y);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
}