[백준] 1012번 유기농 배추 JAVA (자바) 풀이

Baekjoon/[5] DFS & BFS

[백준] 1012번 유기농 배추 JAVA (자바) 풀이

Poorm 푸름 2023. 9. 11. 14:05

문제 1012번(dfs, bfs)

: 배추흰지렁이는 상하좌우 네 방향에 위치한 다른 배추로 이동 가능
: 배추흰지렁이가 있는 배추들은 해충으로부터 보호받을 수 있다

: 예) 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요

0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅

1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0
0	0	1	1	0	1	1	1
0	0	0	0	1	1	1	1

[입력]

: 첫째 줄에는 테스트 케이스 개수 T

: 둘째 줄에는 배추 밭 가로 M, 세로 N, 배추 심은 땅 개수 k
: 셋째 줄부터 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)
(두 배추의 위치가 같은 경우는 없다)

[출력]

: 필요한 최소의 배추흰지렁이 마리 수를 출력

[DFS 코드]

import java.util.*;
import java.io.*;

public class Main {
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	static int arr[][];
	static boolean visit[][];

	static int now_x, now_y;
	static int M, N, K;
	static int count;

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

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

			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			arr = new int[M][N];
			visit = new boolean[M][N];

			for(int j=0; j<K; j++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				arr[x][y] = 1;
			}

			count = 0;
			for(int j=0; j<M; j++) {
				for(int k=0; k<N; k++) {

					if(arr[j][k] == 1 && visit[j][k] == false) {
						count++;
						DFS(j, k);
					}
				}
			}
			sb.append(count).append('\n');
		}

		System.out.println(sb);
	} // End Main
	
	public static void DFS(int x, int y) {
		visit[x][y] = true;

		for(int i=0; i<4; i++) {
			now_x = x + dirX[i];
			now_y = y + dirY[i];

			if(Range_check() && visit[now_x][now_y] == false && arr[now_x][now_y] == 1) {
				DFS(now_x, now_y);
			}

		}
	}

	static boolean Range_check() {
		return (now_x < M && now_x >= 0 && now_y < N && now_y >= 0);
	}
}

[해설]

: static int dirX[] = {0, 0, -1, 1}; 상하좌우 좌표 설정
static int dirY[] = {-1, 1, 0, 0};

: static int arr[][]; 배추밭 2차원 배열 설정
static boolean visit[][]; 방문기록 설정

: static int now_x, now_y; 배추 심은 위치
static int M, N, K; 배추 밭 가로, 세로, 배추 심은 땅 개수
static int count = 0;

: int T = Integer.parseInt(br.readLine());

: for(int i=0; i<T; i++) { 테스트 케이스만큼 반복
st = new StringTokenizer(br.readLine()); 공백 단위로 끊어읽기
M = Integer.parseInt(st.nextToken()); 배추 밭 가로입력
N = Integer.parseInt(st.nextToken()); 배추 밭 세로입력
K = Integer.parseInt(st.nextToken()); 배추 심어진 땅 개수

arr = new int[M][N]; 가로 세로의 배추밭 배열
visit = new boolean[M][N];

   for(int j=0; j<K; j++) {
      st = new StringTokenizer(br.readLine()); 공백 단위로 끊어 읽기
      int x = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 가로 입력
      int y = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 세로 입력
      arr[x][y] = 1;
   }

   for(int j=0; j<M; j++) {
   for(int k=0; k<N; k++) {
if(arr[j][k] == 1 && visit[j][k] == false) { 배추 땅이 1이면서 방문기록이 없다면 dfs 갱신
count++; 결과 카운트 해주기
DFS(j, k);
}
}
}

}

: public static void DFS(int x, int y) { dfs 실행
visit[x][y] = true; 기준 배열 지정
for(int i=0; i<4; i++) { 상하좌우 좌표 갱신
now_x = x + dirX[i];
now_y = y + dirY[i];
if(Range_check() && visit[now_x][now_y] == false && arr[now_x][now_y] == 1) {
DFS(now_x, now_y);
}
}
}

: static boolean Range_check() {
return (now_x < M && now_x >= 0 && now_y < N && now_y >= 0);
}

[BFS 코드]

import java.io.*;
import java.util.*;
import java.awt.*;
public class Main{
    static int M,N,K,count;
    static int dx[]={0,0,1,-1};
    static int dy[]={1,-1,0,0};
    static boolean visit[][];
    static int arr[][];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        
        while(T-->0){
            st = new StringTokenizer(br.readLine());
            M=Integer.parseInt(st.nextToken());
            N=Integer.parseInt(st.nextToken());
            K=Integer.parseInt(st.nextToken());
            
            arr = new int[M][N];
            visit = new boolean[M][N];
            count = 0;
            
            for(int i=0; i<K;i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr[x][y]=1;
            }
            
            for(int i=0; i<M; i++){
                for(int j =0; j<N;j++){
                    if(arr[i][j]==1 &&!visit[i][j]){
                        bfs(i,j);
                    }
                }
            }
            System.out.println(count);
        }
    }
    
    static void bfs(int x, int y){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y));
        visit[x][y]=true;
        
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0; i<4;i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(0<=nx&&nx<M && 0<=ny&&ny<N && !visit[nx][ny] && arr[nx][ny]==1){
                    visit[nx][ny]=true;
                    q.add(new Point(nx,ny));
                }
            } 
        }
        count++;
    }
    
}

[해설]

: static int dirX[] = {0, 0, -1, 1}; 상하좌우 좌표 설정
static int dirY[] = {-1, 1, 0, 0};

: static int arr[][]; 배추밭 2차원 배열 설정
static boolean visit[][]; 방문기록

: static int count; 지렁이 개수

: int T = Integer.parseInt(br.readLine());

: while(T-->0) { 테스트 케이스만큼 반복
st = new StringTokenizer(br.readLine()); 공백 단위로 끊어읽기
M = Integer.parseInt(st.nextToken()); 배추 밭 가로입력
N = Integer.parseInt(st.nextToken()); 배추 밭 세로입력
K = Integer.parseInt(st.nextToken()); 배추 심어진 땅 개수

arr = new int[M][N]; 가로 세로의 배추밭 배열
visit = new boolean[M][N];

count = 0; 지렁이 초기화

   for(int j=0; j<K; j++) {
      st = new StringTokenizer(br.readLine()); 공백 단위로 끊어 읽기
      int x = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 가로 입력
      int y = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 세로 입력
      arr[x][y] = 1;
   }

   for(int i=0; i<M; i++) {
   for(int j=0; j<N; j++) {
if(arr[i][j] == 1 && !visit[i][j]) { 갈 수 있는 땅인지 매번 체크
bfs(i,j); 갈 수 있음 bfs 돌리기
}
}
}

System.out.println(count); 결과 출력

}

: static void bfs(int x, int y) { bfs 실행
Queue<Point> q = new LinkedList<>(); 큐선언
        q.add(new Point(x,y)); Point 좌표 사용
        visit[x][y]=true; 방문처리

        while(!q.isEmpty()){
            Point p = q.poll(); 큐에서 현좌표 꺼내기
            for(int i=0; i<4;i++){
                int nx = p.x+dx[i]; 현좌표 + 이동 = 새좌표 (x)
                int ny = p.y+dy[i]; 현좌표 + 이동 = 새좌표 (y)
                if(0<=nx&&nx<M && 0<=ny&&ny<N && !visit[nx][ny] && arr[nx][ny]==1){ 갈 수 있음 전진
                    visit[nx][ny]=true; 새좌표 방문처리
                    q.add(new Point(nx,ny)); 큐에 새좌표 추가
                }
            }
        }
        count++; 인접한 땅 bfs 검열이 모두 끝나면 지렁이 추가
    }

이제 풀어보러 갈께요 :)

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

1012번: 유기농 배추

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

www.acmicpc.net

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시

1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0
0	0	1	1	0	1	1	1
0	0	0	0	1	1	1	1

1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0
0	0	1	1	0	1	1	1
0	0	0	0	1	1	1	1

1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0
0	0	1	1	0	1	1	1
0	0	0	0	1	1	1	1