[Java] 백준 1012번 [유기농 배추] 자바

: ) YOUNG·2022년 3월 23일
DFS/BFSJavaalgorithm백준
2

알고리즘

목록 보기
65/411
post-thumbnail

백준 1012번
https://www.acmicpc.net/problem/1012

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

생각하기

DFS와 BFS둘 다 모두 사용할 수 있는 문제이기 때문에 2가지 방식을 모두 사용했다.

기존에 풀었던 문제들은 전체를 탐색한다고 했다면,
이번에는 이걸 아주 약간? 응응한 문제라고 보면 될 것 같다

1이 나오는 즉, 배추가 나오는 경우에만 BFS건 DFS건 탐색을 하면 된다.

0을 만나게 되면 자동으로 종료되기 때문에 1을 찾는다 생각하면 된다.

DFS

DFS는 재귀 함수와 stack을 사용해 둘 다 구현해보았다.

배추밭을 표현한 map에서 1인 곳과 visit 이 false인 곳이 나올 경우
DFS를 실행해서 탐색한다.

그리고 1인 구역에서 연결된 곳은 벌레가 한마리만 있으면 되므로 DFS가 실행되기 전에 count를 증가시켜주어 1만 증가시켜주도록 한다.

DFS 함수는 사실 1인 구역을 탐색하긴 하지만, 어떻게 보면 0을 찾는다 라고도 말할 수 있다. DFS는 0을 만났을 때 재귀가 종료되니까 반대로 생각하면 더 이해하기가 수월할 수 있다고 생각한다.

stack은 BFS의 Queue를 그냥 stack으로 바꾸기만 하면되니까, BFS를 할 줄 아는 사람은 진짜 간단하게 구현할 수 있다.

BFS

BFS는 Queue를 사용하니까 static을 통해서 que를 미리 생성해주었다.

DFS와 마찬가지로 map에서 1인 곳과 visit 이 false인 곳이 나올 경우
BFS를 실행해서 탐색한다.

BFS도 방문한 1이 없는 상태에서 0이 나오게되면 que가 자동으로 점점 비게 될 것이고 que가 비면 또 빠져나와서 다른 배추가 있는지 탐색하는 것이다.

TMI

혹시 궁금해서 진짜 배추흰지렁이 라는 지렁이가 있는지 검색해봤는데
없는 지렁이였네..

코드

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 map[][];
	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());

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

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

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

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

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

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

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

		}
	}

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

} // End Class

DFS stack 사용

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

public class Main {
	static Stack<Node> stack = new Stack<>();	
	static int map[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};

	static int count = 1;
	static int N, M;
	static int nowX, nowY;
	
	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	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());
		while(T--> 0) {
			st = new StringTokenizer(br.readLine());

			M = Integer.parseInt(st.nextToken()); // 가로
			N = Integer.parseInt(st.nextToken()); // 세로

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

			int K = Integer.parseInt(st.nextToken());
			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[y][x] = 1;
			}

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

					if(visit[i][j] == false && map[i][j] == 1) {
						count ++;			
						DFS(j, i);
					}
				}
			}
			sb.append(count).append('\n');
		} 
		
		System.out.println(sb);
	} // End of main
	
	static void DFS(int x, int y) {
		stack.add(new Node(x, y));
		visit[y][x] = true;
		
		while( !stack.isEmpty() ) {
			Node node = stack.pop();
			
			for(int i=0; i<4; i++) {
				nowX = node.x + dirX[i];
				nowY = node.y + dirY[i];
				
				if( Range_check() && visit[nowY][nowX] == false && map[nowY][nowX] == 1) {
					stack.push(new Node(nowX, nowY));
					visit[nowY][nowX] = true;
				}
			}	
		}
	}
	
	static boolean Range_check() {
		return (nowX < M && nowY < N && nowX >= 0 && nowY >= 0);
	}
}

BFS 사용

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

public class Main {
	static Queue<Node> que = new LinkedList<>();
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	static int map[][];
	static boolean visit[][];

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

	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	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());

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

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

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

					if(visit[j][k] == false && map[j][k] == 1) {
						count++;
						BFS(k, j);
					}
				}
			}

			sb.append(count).append('\n');
		}		

		System.out.println(sb);
	}

	static void BFS(int x, int y) {
		que.offer(new Node(x, y));
		visit[y][x] = true;

		while( !que.isEmpty() ) {
			Node node = que.poll();

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

				if(Range_check() && visit[now_y][now_x] == false && map[now_y][now_x] == 1) {           
					que.offer(new Node(now_x, now_y));
					visit[now_y][now_x] = true;
				}

			}
		}
	}

	public static boolean Range_check() {
		return (now_x >= 0 && now_x < M && now_y >= 0 && now_y < N);
	}	
}
profile
: ) YOUNG
이전 포스트

백준 2178 미로 탐색 Java

다음 포스트

[Java] 백준 7576번 [토마토] 자바

0개의 댓글