백준 11060: 점프 점프[JAVA]

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

 

[난이도]

- Silver 2

 

[알고리즘]

- BFS

 

[코드]

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

public class Main {
    static char[][] graph;
    static boolean[][] visited;
    static int T, H, W, answer = 0;
    static Queue<int[]> queue;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {-0, 0, -1, 1};
    static ArrayList<int[]> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            graph = new char[H][W];
            visited = new boolean[H][W];
            queue = new LinkedList<>();
            list = new ArrayList<>();
            answer = 0;
            for (int j = 0; j < H; j++) {
                String input = br.readLine();
                for (int k = 0; k < W; k++) {
                    graph[j][k] = input.charAt(k);
                }
            }
            for (int j = 0; j < H; j++) {
                for (int k = 0; k < W; k++) {
                    if (graph[j][k] == '#') { // 양일경우
                        if (!visited[j][k]) { // 방문하지 않은 곳일 경우 bfs 메서드 실행
                            queue.offer(new int[]{j, k});
                            visited[j][k] = true;
                            bfs();
                            answer++;
                        }
                    }
                }
            }
            bw.write(answer + "\n");

        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < H && ny >= 0 && ny < W) { // 인덱스 범위 안
                    if (graph[nx][ny] == '#') { // 양일 경우
                        if (!visited[nx][ny]) { // 방문하지 않은경우
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    }
}

 

[풀이]

1. for문을 돌며 탐색한 위치가 양(#)이면서 체크하지않은 양일경우 bfs()를 실행하고 answer++한다.

2. bfs는 4방탐색을 하며 인덱스 범위 안이면서 양이면서 방문하지 않은 경우 새로 탐색한 위치를 큐에 담는다.

3. answer를 출력한다.