import java.util.*; public class BOJ1012 { static class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } static int[][] arr; // 최대 50 * 50 static int[][] visited; static int[] dx = { 0, 0, -1, 1 }; static int[] dy = { -1, 1, 0, 0 }; static int N; // 가로 static int M; // 세로 static int K; // 배추가 심어진 갯수 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int t = 0; t < testCase; t++) { int N = sc.nextInt(); int M = sc.nextInt(); int K = sc.nextInt(); // System.out.println(N + " " + M + " " + K); arr = new int[N][M]; // 배추밭 visited = new int[N][M]; // 방문체크 for (int i = 0; i < K; i++) { int tempX = sc.nextInt(); int tempY = sc.nextInt(); //System.out.println("tempX: " + tempX); arr[tempX][tempY] = 1; } Queue queue = new LinkedList(); int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (arr[i][j] == 1 && visited[i][j] == 0) { queue.add(new Pair(i, j)); bfs(queue, N, M); cnt++; } } } System.out.println(cnt); } } public static void bfs(Queue queue, int N, int M) { while (!queue.isEmpty()) { Pair p = queue.poll(); int x = p.x; int y = p.y; visited[x][y] = 1; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx > 0 && nx < N && ny > 0 && ny < M) { if (arr[nx][ny] == 1 && visited[nx][ny] == 0) { visited[nx][ny] = 1; queue.add(new Pair(nx, ny)); } } } } } }// class end

제출 #16869

제출 정보

제출 결과

제출 코드

찾은 반례