[알고리즘] 양 한마리, 양 두마리 - bfs

문제 링크 : https://www.acmicpc.net/problem/11123

public class P11123 {
    static boolean[][] visited;
    static int x, y;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            char[][] chars = new char[x][y];
            visited = new boolean[x][y];

            for (int j = 0; j < x; j++){
                chars[j] = br.readLine().toCharArray();
            }

            int result = solution(chars);

            System.out.println(result);
        }
    }

    private static int solution(char[][] chars) {
        int count = 0;
        for (int i = 0; i < x; i++){
            for (int j = 0; j < y; j++){
                if (chars[i][j] == '#'){
                    if (!visited[i][j]){
                        count++;
                        bfs(chars, i, j);
                    }
                }
            }
        }
        return count;
    }

    private static void bfs(char[][] chars, int startX, int startY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        while (!queue.isEmpty()){
            int[] s = queue.poll();

            for (int i = 0; i < 4; i++){ // 동서남북 체크 [동, 남, 서, 북]
                // static int dx[] = {0, 1, 0, -1};
                // static int dy[] = {1, 0, -1, 0};
                int num1 = s[0] + dx[i];
                int num2 = s[1] + dy[i];

                // 경계값을 벗어나지 않으면서 방문하지 않았고, 양인것을 찾는다.
                if (0 <= num1 && num1 < x && 0 <= num2 && num2 < y && !visited[num1][num2] && chars[num1][num2] == '#'){
                    queue.add(new int[]{num1, num2});
                    visited[num1][num2] = true;
                }
            }
        }
    }
}

풀이 과정

• 1, 양의 무리를 체크해주기 위하여 동서남북 검사를 하기 위해 dx, dy를 선언해주었으며, 방문한 곳인이 확인하기 위해 똑같은 2차원 배열인 visited를 선언해주었다.

• 2, main 함수는 입력을 받는 곳이며 2차원 배열을 입력받기 위해 toCharArray()를 선언해주었다.

• 3, solution 함수에서 2차원 배열을 순회하며 visited = false일 경우와 # 양일 경우에 count를 증가시키고 bfs로 들어가게 된다. (이때 좌표값과 배열을 같이 보낸다.)

• 4, 우선 받은 startX와 startY를 queue에 넣어준다. (queue의 내부는 배열형식으로 저장했다.) 또한, 현재 들어온 위치는 방문한 곳이기 때문에 좌표를 true값으로 선언해주었다.

• 5, while문을 통해 queue가 빈 상태일때까지 순회를 한다. queue poll하여 좌표를 s 배열에 넣어준다.

• 6, 동서남북으로 순회를 하기 위하여 4번만큼 for문을 순회해주고 num1과 num2값을 통해 동서남북을 테스트한다.

• 7, 0 <= num1 && num1 < x && 0 <= num2 && num2 < y로 경계값을 확인하고 !visited[num1][num2] && chars[num1][num2] == '#' 를 통하여 방문하지 않고 양인지 확인한다.

• 8, 만약에 모든 조건을 만족한다면 queue에 값을 num1과 num2를 넣어주고 visited에 true값을 세팅해준다. 여기서 true값으로 세팅해주는 이유는 solution에서 false값으로 되어있으면 다시 한번 중복체크를 하기 때문에 true값을 넣어주어야 한다.