[백준 1012번] 유기농 배추

문제 링크: 1012번 제목

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

 

연결된 노드의 집합의 개수를 구하는 문제이다. 앞선 문제처럼, visited를 선언하지 않고도 0, 1, 2로 구분하는 방식으로 해서 문제를 풀어갈 수도 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
​​​​static int[] drow = {0, 0, 1, -1};
​​​​static int[] dcol = {1, -1, 0, 0};

​​​​static class Pos {
​​​​​​​​int row;
​​​​​​​​int col;

​​​​​​​​Pos(int row, int col) {
​​​​​​​​​​​​this.row = row;
​​​​​​​​​​​​this.col = col;
​​​​​​​​}
​​​​}

​​​​static void bfs(int i, int j, int[][] map, boolean[][] visited, int m, int n) {
​​​​​​​​Queue<Pos> queue = new LinkedList<>();
​​​​​​​​queue.offer(new Pos(i, j));

​​​​​​​​while (!queue.isEmpty()) {
​​​​​​​​​​​​Pos cur = queue.poll();
​​​​​​​​​​​​int row = cur.row;
​​​​​​​​​​​​int col = cur.col;

​​​​​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​​​​​int nrow = row + drow[d];
​​​​​​​​​​​​​​​​int ncol = col + dcol[d];

​​​​​​​​​​​​​​​​if (nrow<0 || ncol<0 || nrow>=n || ncol>=m || visited[nrow][ncol] || map[nrow][ncol]!=1)
​​​​​​​​​​​​​​​​​​​​continue;

​​​​​​​​​​​​​​​​visited[nrow][ncol] = true;
​​​​​​​​​​​​​​​​queue.offer(new Pos(nrow, ncol));
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​static void solution(int m, int n, int[][] map) {
​​​​​​​​boolean[][] visited = new boolean[n][m];

​​​​​​​​int cnt = 0;
​​​​​​​​for (int i = 0; i < n; i++)
​​​​​​​​​​​​for (int j = 0; j < m; j++)
​​​​​​​​​​​​​​​​if (!visited[i][j] && map[i][j]==1) {
​​​​​​​​​​​​​​​​​​​​visited[i][j] = true;
​​​​​​​​​​​​​​​​​​​​bfs(i, j, map, visited, m, n);
​​​​​​​​​​​​​​​​​​​​cnt++;
​​​​​​​​​​​​​​​​}

​​​​​​​​System.out.println(cnt);
​​​​}

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

​​​​​​​​for (int tc = 0; tc < tcs; tc++) {
​​​​​​​​​​​​int[] temp1 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
​​​​​​​​​​​​int m = temp1[0];
​​​​​​​​​​​​int n = temp1[1];
​​​​​​​​​​​​int k = temp1[2];

​​​​​​​​​​​​int[][] map = new int[n][m];
​​​​​​​​​​​​for (int i = 0; i < k; i++) {
​​​​​​​​​​​​​​​​int[] temp2 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
​​​​​​​​​​​​​​​​map[temp2[1]][temp2[0]] = 1;
​​​​​​​​​​​​}

​​​​​​​​​​​​solution(m, n, map);
​​​​​​​​}

​​​​​​​​br.close();
​​​​}
}