[BOJ 1388] 바닥 장식 - JAVA

이번엔 오랜만에 BFS 문제를 풀었습니다.

오랜만에 푸는 거라 그런지 노드 클래스 생성하는거 부터 난관 봉착,,,,

그래도 가장 많이 푼 알고리즘이라 그런지 빠르게 적응하고 풀었습니다,,,

 

BFS 중에서 쉬운 문제였습니다.

 

구현내용

 

구현방법

가장 중요한 방법은 - 모양일땐 bfs 방향을 가로로만 증가

| 모양일땐 bfs 방향은 세로로만 증가하는 것입니다.

 

자세한 내용은 주석을 통해하도록 하겠습니다.

↓↓↓↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓  ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

 

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

public class main {
    static int[] dx = {1,-1};   //"|" 일떄 방향
    static int[] dy = {1,-1};   //"-" 일때 방향
    static String[][] tile;     // 타일 배열
    static boolean[][] visited; // 방문 배열
    static int n;   // 세로
    static int m;   //가로

    static class node{ 
        int x;
        int y;

        node(int x, int y){
            this.x = x;
            this.y = y;
        }
        int getX(){
            return x;
        }
        int getY(){
            return y;
        }
    }
    static void bfs(int x, int y){
        Queue<node> q = new LinkedList<>();
        q.add(new node(x, y));
        while(!q.isEmpty()) {   //큐가 비어있지 않다면
            node node = q.poll();   // 큐에 담겨있는 노드를 뺴내서
            x = node.getX();
            y = node.getY();
            for(int i=0;i<2;i++){   //위에 설정한 방향 배열만큼 돈다
                int nx = x;
                int ny = y;
                if(tile[x][y].equals("-")){ //- 모양 타일이라면 행만 확인
                    ny = y+dy[i];
                }
                if(tile[x][y].equals("|")){ //| 모양 타일이라면 열만 확인
                    nx = x+dx[i];
                }
                if(nx < 0 || ny < 0 || nx > n-1 || ny > m-1)    //array exception 확인
                    continue;
                if(visited[nx][ny]==true)   //방문했다면 확인하지 않는다
                    continue;
                if(tile[nx][ny].equals(tile[x][y])){    //다음 방향의 타일이 비교 타일과 같다면 
                    visited[nx][ny] = true; //  방문하고
                    q.add(new node(nx, ny));//큐에 넣는다
                }
                else{   // 같지 않다면 bfs 탈출
                    return;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st  = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        tile = new String[n][m];
        visited = new boolean[n][m];
        int count = 0;
        for(int i=0;i<n;i++){
            String line = br.readLine();
            for(int j=0;j<m;j++){
                tile[i][j] = String.valueOf(line.charAt(j));
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j]==false){ //방문 하지 않았다면
                    visited[i][j] = true;   //방문하고
                    bfs(i,j);   //bfs 돌고
                    count++;    // 필요 타일 개수 증가
                }
            }
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }
}