𝙰𝚕𝚐𝚘𝚛𝚒𝚝𝚑𝚖/𝙱𝚊𝚎𝚔𝚓𝚘𝚘𝚗

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

해버니 2023. 12. 19. 09:51
반응형

 

 

문제

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 

 

 

 

 

 

 

 

 

 

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static boolean[][] visited; // 방문 여부
    public static int[][] graph;
    public static int count;
    public static int[] dx = {0, -1, 0, 1};
    public static int[] dy = {-1, 0, 1, 0};

    /**
     * 상하좌우로 이어져 있으면 탐색
     * 
     * @param x
     * @param y
     */
    public void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];

            if (cx >= 0 && cy >= 0 && cx < graph.length && cy < graph[0].length) {
                if (graph[cx][cy] == 1 && visited[cx][cy] == false) {
                    dfs(cx, cy);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Main mm = new Main();

        int T = Integer.parseInt(br.readLine()); // 테스트케이스 수

        for (int i = 0; i < T; i++) {
            count = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            graph = new int[n + 1][m + 1];
            visited = new boolean[n + 1][m + 1];

            for (int j = 0; j < graph.length; j++) {
                for (int l = 0; l < graph[0].length; l++) {
                    visited[j][l] = false; // 방문여부 초기화
                }
            }

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph[b][a] = 1;
            }

            for (int j = 0; j < graph.length; j++) {
                for (int l = 0; l < graph[0].length; l++) {
                    if (visited[j][l] == false && graph[j][l] == 1) {
                        mm.dfs(j, l);
                        count++;
                    }
                }
            }
            bw.write(String.valueOf(count) + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

 

 

정답

 

 

 

 

 

 

반응형