99클럽 코테 스터디 34일차 TIL (BFS)

JAVA / Lv 실버 II. 양 한마리.. 양 두 마리

 

문제

양을 # 으로 나타내고 . 으로 풀을 표현한다. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는것이다.
다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

 

입력사항

첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.

이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진 문자열 하나를 입력받는다. 

0 < T ≤ 100
0 < H, W ≤ 100

 

입출력 예

문제 해결

상하좌우를 살펴야 한다는 것에 BFS를 사용해야겠다고 생각했습니다.
"#" 하나마다 answer가 +1 되지만 상하좌우에 연결되어있는것이 있다면 그 묶음 전체가 하나가 됩니다.
주의할 점은 두 번의 테스트 케이스를 실행해야 된다는 점이고 각 테스트 마다 answer가 초기화 되어야합니다.

2차원 배열에서 #은 1로 저장하고 아닌경우 0으로 저장합니다.
방문여부를 기록하고 최초로 방문하지 않은 1이 있다면 BFS를 실행합니다.

BFS에서 상하좌우 인접노드를 확인합니다.
1인 인접노드가 있다면 해당 노드들을 전부 큐에 삽입, 전부 방문 처리 시켜버립니다.
이미 큐에 담겨져있는 방문처리된 노드들은 의미없이 while문 안에 for문만 실행한 뒤 큐가 비워지면 종료됩니다.
1인 인접노드가 없다면 큐에 삽입된 데이터가 없으니 그대로 종료되고 answer++합니다.

상하좌우 탐색 시 배열 범위를 벗어나지 않도록 예외처리를 같이 해줬습니다.

나의 풀이

package BFS;

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

public class BFS02 {
    static int[][] map;
    static int H,M;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer;
        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            answer = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            map = new int[H+1][M+1];
            visited = new boolean[H+1][M+1];

            for (int i = 0; i < H; i++) {
                String str = br.readLine();
                for (int j = 0; j < M; j++) {
                    if(str.charAt(j) == '#'){
                        map[i][j] = 1;
                    }else{
                        map[i][j] = 0;
                    }
                }
            } // 0 또는 1 삽입

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < M; j++) {
                    if(map[i][j] == 1 && !visited[i][j]){
                        BFS(i, j);
                        answer++;
                    }
                }
            }

            System.out.println(answer);
        }

    }

    static void BFS(int x, int y) throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visited[x][y] = true;

        while (!q.isEmpty()){
            int[] arr = q.poll();
            int al = arr[0] , ar = arr[1];

            for (int i = 0; i < 4; i++) {
                int nx = al + dx[i];
                int ny = ar + dy[i];

                if (nx < 0 || ny < 0 || nx >= H || ny >= M) continue;

                if(!visited[nx][ny] && map[nx][ny] == 1){
                    q.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}