백준 1388번 바닥 장식 JAVA

링크텍스트

설명

재귀를 사용해서 풀었다.
시간복잡도: O(N*M), 공간복잡도: O(N*M)

코드

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

class Main {
		static int n,m;
        static char [][] arr;
        static boolean [][] check; 
        static int count = 0;
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    
	    n = Integer.parseInt(st.nextToken());
	    m = Integer.parseInt(st.nextToken());
	    
	    arr = new char [n][m];
	    check = new boolean[n][m];
	    
	    for(int i=0;i<n;i++){
	        String s = br.readLine();
	        for(int j=0;j<m;j++){
	            arr[i][j] = s.charAt(j);
	        }
	    }
	    
	    for(int i=0;i<n;i++){
	        for(int j=0;j<m;j++){
	            if(!check[i][j]){
	                find(i,j,arr[i][j]);
					count++;
	            }
	        }
	    }

		System.out.println(count);
	}
	
	public static void find(int x,int y,char floor){
	    check[x][y]=true;
	    if(floor == '-' && y+1<m && !check[x][y + 1] && arr[x][y + 1] == '-'){
	        find(x,y+1,'-');
	    }else if(floor == '|' && x+1<n && !check[x + 1][y] && arr[x + 1][y] == '|'){
	        find(x+1,y,'|');
	    }
	}
}