[백준(Baekjoon)][자바(java)] 2667 : 단지번호 붙이기 / DFS와 BFS

 

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

1. Recursion

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

public class Main {
	
	static int n, m[][], cnt;
	static boolean v[][];
	static List<Integer> home = new ArrayList<>();
	
	public static void getArea_DFS( int x, int y ) {
		if( x < 0 || y < 0 || x >= n || y >= n )
			return;
		if( v[x][y] )
			return;
		v[x][y] = true;
		cnt++;
		getArea_DFS( x+1, y );
		getArea_DFS( x-1, y );
		getArea_DFS( x, y+1 );
		getArea_DFS( x, y-1 );
	}
	
	public static void cntZone() {
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < n; j++ ) {
				if( !v[i][j] ) {
					cnt = 0;
					DFS( i, j );
					home.add( cnt ); 
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		n = Integer.parseInt( br.readLine() );
		m = new int[n][n];
		v = new boolean[n][n];
		for( int i = 0; i < n; i++ ) {
			String s = br.readLine();
			for( int j = 0; j < n; j++ )
				m[i][j] = s.charAt(j)-'0';
		}
		br.close();
		
		for( int i = 0; i < n; i++ )
			for( int j = 0; j < n; j++ )
				if( m[i][j] == 0 )
					v[i][j] = true;

		cntZone();
		
		Collections.sort( home );
		bw.write( home.size() + "\n" );
		for( int z : home )
			bw.write( z + "\n" );
		
		bw.flush();
		bw.close();
	}
}

 

2. Stack

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

public class Main {
	
	static int n, m[][], cnt, dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
	static boolean v[][];
	static List<Integer> home = new ArrayList<>();
	
	static class Cell {
		int x;
		int y;
		public Cell( int x, int y ) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int getArea_DFS( int x, int y ) {
		
		Stack<Cell> stack = new Stack<>();
		stack.add( new Cell( x, y ) );
		v[x][y] = true;
		int cnt = 0;
		while( !stack.empty() ) {
			Cell c = stack.pop();
			for( int i = 0; i < 4; i++ ) { // 상하좌우
				int x_n = c.x + dx[i];
				int y_n = c.y + dy[i];
				if( 0 <= x_n && x_n < n && 0 <= y_n && y_n < n 
				    && !v[x_n][y_n] && m[x_n][y_n] == 1 ) {
					stack.add( new Cell( x_n, y_n ) );
					v[x_n][y_n] = true;
					cnt++;
				}
			}
		}
		return cnt;
	}
	
	public static void cntZone() {
		for( int i = 0; i < n; i++ ) 
			for( int j = 0; j < n; j++ ) 
				if( !v[i][j] && m[i][j] == 1 ) 
					home.add( getArea_DFS( i, j ) ); 
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		n = Integer.parseInt( br.readLine() );	// map size
		m = new int[n][n];	// map arr
		v = new boolean[n][n];
		for( int i = 0; i < n; i++ ) {
			String s = br.readLine();
			for( int j = 0; j < n; j++ )
				m[i][j] = s.charAt(j)-'0';
		}
		br.close();

		cntZone();
		
		Collections.sort( home );
		bw.write( home.size() + "\n" );
		for( int z : home )
			bw.write( z + "\n" );
		
		bw.flush();
		bw.close();
	}
}