[백준] 1012번: 유기농 배추 - JAVA

 

문제

 

 

 

 

 

풀이

전체 배추밭을 2차 배열 구조로 만듭니다.

배추의 위치를 입력받아 해당 위치를 1로 변경합니다.

배추밭의 0, 0부터 마지막까지 반복하며 배추가 있고, 방문하지 않은 경우 인접한 배추를 모두 찾아 방문으로 변경하고

변경이 완료되면 지렁이의 수를 1 증가시킵니다.

인접한 배추는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 찾습니다.

배추의 위치에서 상하좌우를 확인하여 배추가 있는 경우 방문으로 변경하고,

그 배추의 위치에서 다시 탐색하여 인접한 배추를 모두 찾습니다.

 

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int count;
	static int[][] map;
    static boolean[][] visited;

    static int[] dx = {1, 0 , -1, 0};       // 상하좌우 계산할 x좌표
    static int[] dy = {0, 1, 0, -1};        // 상하좌우 계산할 y좌표

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        count = Integer.parseInt(br.readLine());
        for(int m = 0 ; m < count; m++){
            int wormCount = 0;

            st = new StringTokenizer(br.readLine(), " ");
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            map = new int[M][N];
            visited = new boolean[M][N];
            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }

			// 0,0부터 끝까지 반복
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < N; j++) {
                	// 방문하지 않은 배추라면
                    if(map[i][j] == 1 && !visited[i][j]) {
                        cabbageDfs(i, j);
                        wormCount++;
                    }
                }
            }

            System.out.println(wormCount);
        }
    }
    
    static void cabbageDfs(int i, int j) {
        visited[i][j] = true;
        for(int k=0; k<4; k++) {
            int nx = dx[k]+i;
            int ny = dy[k]+j;
            // 방문하지 않은 인접 배추라면
            if(nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length && map[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                cabbageDfs(nx,ny);
            }
        }
    }
}

 

 

 

문의사항이나 피드백은 댓글로 남겨주세요.