[백준] 1926번 : 그림

문제

1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

 

위와 같은 입력이 주어졌을 때

그림의 개수와 가장 큰 그림의 사이즈를 출력하는 문제

 

접근 방식

 

위의 입력에서는 총 4개의 그림이 있고

가장 큰 그림의 사이즈는 9라는 것을 알 수 있다.

 

눈으로 보면 당연한 거지만 이를 코드로 구현하는 것이

BFS를 처음 배우고 푸는 문제라서 많이 어려웠다...

 

우선 입력 받은 값들을 그림 배열에 저장해 준 후에

해당 그림 배열을 돌면서 찾아주면 된다.

 

이때 방문한 배열을 다시 방문하지 않기 위해

0이나 1 혹은 true false로 방문 여부를 저장할 배열을 만들어 기록해 준다.

 

Queue<Pair> Q = new LinkedList<>();
isVisited[0][0] = true;
Q.add(new Pair(0, 0));

while (!Q.isEmpty()) {
    Pair cur = Q.poll();
    System.out.print("(" + cur.x + ", " + cur.y + ") -> ");
    for (int dir = 0; dir < 4; dir++) {
        int nx = cur.x + dx[dir];
        int ny = cur.y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (isVisited[nx][ny] || board[nx][ny] != 1) continue;
        isVisited[nx][ny] = true;
        Q.add(new Pair(nx, ny));
    }
}

 

기본적인 BFS 알고리즘의 구조는 위와 같이

현재 위치에 상하좌우를 확인하는 방식이다.

 

코드를 보면 알 수 있듯이 이미 방문했거나 값이 1이 아닌 경우에는

방문하지 않고 넘어가는데 이 과정을 통해

1이 끊기지 않고 연결된 수를 알 수 있다.

 

즉, 그림 하나의 사이즈를 알 수 있는데

문제에서는 추가적으로 그림의 개수도 세어줘야 하기 때문에

그림의 시작점을 찾아서

해당 시작점마다 그림의 개수를 1씩 증가시키고

BFS 알고리즘을 적용하여 사이즈를 계산해 주면 된다.

 

풀이

public class Main {

	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};

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

		String[] nm = br.readLine().split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);

		int[][] painting = new int[n][m];

		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");

			for (int j = 0; j < m; j++) {
				painting[i][j] = Integer.parseInt(input[j]);
			}
		}

		boolean[][] isVisited = new boolean[502][502];

		int max = 0;
		int count = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (painting[i][j] == 0 || isVisited[i][j]) continue;
				count++;
				Queue<Pair> queue = new ArrayDeque<>();

				isVisited[i][j] = true;
				queue.offer(new Pair(i, j));

				int area = 0;

				while (!queue.isEmpty()) {
					area++;
					Pair cur = queue.poll();

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.x + dx[dir];
						int ny = cur.y + dy[dir];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (isVisited[nx][ny] || painting[nx][ny] != 1) continue;

						isVisited[nx][ny] = true;
						queue.offer(new Pair(nx, ny));
					}

					max = Math.max(max, area);
				}
			}
		}

		System.out.println(count + "\n" + max);
	}

	private static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}