[백준 1012] 유기농 배추(Java)

1. 문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

2. 풀이

• DFS를 사용하여 풀이하였다.
• 배추가 심어져 있는 땅을 1로 표기하여, 2중 for문에서 1을 만났을 때 visited를 true로 해주었다.
• 방문하지 않은 배추자리에 갔을 때마다 카운트하여 배추가 모여있는 땅의 갯수를 구하였다.

3. 코드

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

public class Main {

	static int N,M;
	static int[][] map;
	static boolean[][] visited;
	static int[][]dir ={{-1,0},{0,1},{1,0},{0,-1}};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new StringReader(src));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int num = Integer.parseInt(st.nextToken());
		while(num-->0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			visited = new boolean[N][M];
			int count = Integer.parseInt(st.nextToken());
			for(int i =0; i<count; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				map[a][b]=1;
			}
			int cnt=0;
			for(int i =0; i<N; i++) {
				for(int j =0; j<M;j++) {
					if(!visited[i][j] && map[i][j]==1) {
						visited[i][j]= true;
						cnt++;
						dfs(i,j);
					}
				}
			}
			System.out.println(cnt);
			
		}
		
	}
	static void dfs(int r, int c) {
		for(int d=0; d<4; d++) {
			int newR = r +dir[d][0];
			int newC = c +dir[d][1];
			if(isRange(newR, newC) && map[newR][newC]==1 && !visited[newR][newC]) {
				visited[newR][newC] = true;
				dfs(newR, newC);
			}
		}
	}
	static boolean isRange(int r, int c) {
		return r>=0 && c>=0 && r<N && c<M;
	}
	
	static String src = 
			"2\r\n" + 
			"10 8 17\r\n" + 
			"0 0\r\n" + 
			"1 0\r\n" + 
			"1 1\r\n" + 
			"4 2\r\n" + 
			"4 3\r\n" + 
			"4 5\r\n" + 
			"2 4\r\n" + 
			"3 4\r\n" + 
			"7 4\r\n" + 
			"8 4\r\n" + 
			"9 4\r\n" + 
			"7 5\r\n" + 
			"8 5\r\n" + 
			"9 5\r\n" + 
			"7 6\r\n" + 
			"8 6\r\n" + 
			"9 6\r\n" + 
			"10 10 1\r\n" + 
			"5 5";
}

반응형