[JAVA] 백준 1388번- 바닥 장식

https://www.acmicpc.net/problem/1388

1388번: 바닥 장식

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static int[] d = {-1, 1};
    static int n, m;
    static char[][] arr;
    static boolean[][] visit;
    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]; // 바닥 배열
       visit = new boolean[n][m]; // 방문 처리

       for(int i=0; i<n; i++){
           String str = br.readLine();
           for(int j=0; j<m; j++){
               arr[i][j] = str.charAt(j);
           }
       }

        int cnt=0;

       for(int i=0; i<n; i++){
           for(int j=0; j<m; j++){
               if(!visit[i][j]){
                   dfs(i,j);
                   cnt++;
               }
           }
       }

        System.out.println(cnt);

    }

    public static void dfs(int x, int y){

        visit[x][y] = true; // 방문 체크

        for(int i=0; i<2; i++){
            int nx =x, ny = y;
            
            if(arr[x][y] == '|') nx += d[i]; // 다음 세로칸 탐색
            else ny += d[i]; // 다음 가로칸 탐색
            
            if(nx>=0 && ny>=0 && nx<n && ny<m){ // 범위 내에 있다면
                if (arr[nx][ny] == arr[x][y] & !visit[nx][ny]) { // 이전 칸과 같은 모양이고 방문하지 않았다면
                    dfs(nx, ny); // dfs 호출
                }
            }
        }
    }
}

 

현재 칸이 - 일 경우 다음 가로칸을, 현재 칸이 | 일 경우 세로칸을 탐색한다.

다음 칸이 현재 칸과 다른 모양이라면 탐색을 하지 않는다. 

탐색한 칸일 경우 방문 처리를 해준다.

이런식으로 모든 칸 중 방문하지 않은 칸에서만 dfs를 실행해 외부에서 실행한 dfs의 횟수를 카운팅 해주면 된다.