[Eric's 백준] 1012번 - 유기농배추 🥬 - Java

문제

안녕하세요! Eric 입니다! 오늘 풀어볼 문제는

백준 1012번 , 유기농 배추 입니다!

그러면 문제를 풀어보도록 하죠!

 

풀이

우선 유기농배추를 만들기위해서 배추흰지렁이 를 깔아야합니다.

깔기위해서는 배추가 있는 위치에 깔아야며, 그 지렁이가 상하좌우 로 움직이면서 배추를 보호한다

이를 저는 dfs를 통해서 구연해 보았습니다.

 

우선 주어진 test case를 int로 받고,

그때의 주어진 배추밭의 길이 m과 n을 받아서

이를 통해서 boolean[] graph를 만듭니다.

이는 배추가 있는 위치에 true값을 주며,

배추가 없는 위치에는 false로 만들어줍니다.

 

그리고 동일한 사이지의 boolean[] visited 배열을 만들고

dfs가 돌면서 해당 지점을 방문하면 true로 값을 변환해줍니다.

 

코드

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	class N1012 {
	static boolean[][] graph;
	static boolean[][] visited;
	static int n, m, k, answer;
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {1, 0, -1, 0};
	public static void main(String[] args) throws IOException {
	// 0. 입력 및 초기화
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int tc = Integer.parseInt(br.readLine());
	for (int i = 0; i < tc; i++) {
	answer = 0;
	StringTokenizer st = new StringTokenizer(br.readLine());
	m = Integer.parseInt(st.nextToken());
	n = Integer.parseInt(st.nextToken());
	k = Integer.parseInt(st.nextToken());
	// 1. 그래프 정보 입력
	graph = new boolean[m][n];
	visited = 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());
	graph[x][y] = true;
	}
	for (int g = 0; g < m; g++) {
	for (int h = 0; h < n; h++) {
	if (graph[g][h] && !visited[g][h]) {
	dfs(g, h);
	answer++;
	}
	}
	}
	System.out.println(answer);
	}
	br.close();
	}
	//bfs를 돌면서 해당 위치를 방문했다고 표시하기
	public static void dfs(int x, int y) {
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
	for (int j = 0; j < 4; j++) {
	int cx = x + dx[i];
	int cy = y + dy[i];
	if (cx >= 0 && cy >= 0 && cx < m && cy < n) {
	if (!visited[cx][cy] && graph[cx][cy]) {
	dfs(cx, cy);
	}
	}
	}
	}
	}
	}

view raw N1012.java hosted with ❤ by GitHub