[백준] [1926] 그림

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

1926번: 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 복사

6 5
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

예제 출력 1 복사

4
9

 

---

※ JAVA 코드 (그림)

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

public class Main {
	// 초기화
	static int N, M;
	// 초기 맵을 위한 배열
	static int [][] map;
	
	// 방문 체크를 위한 배열
	static boolean [][] visited;
	
	// 상하좌우 이동 좌표
	static int [] dx = {-1, 1, 0, 0};
	static int [] dy = {0, 0, -1, 1};
	
	// 각 좌표를 담을 노드
	static class Node {
		int x, y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	// BFS
	public static int BFS(int x, int y) {
		// 순서를 담을 
		Queue<Node> q = new LinkedList<>();
		// 큐에 시작 좌표를 담는다.
		q.offer(new Node(x, y));
		// 초기방문 체크
		visited[x][y] = true;
		int cnt = 0;
		// 큐가 빌때까지 반복
		while(!q.isEmpty()) {
			// 현재 좌표
			Node now = q.poll();
			cnt++;
			// 상하좌우 이동할 좌표 찾기
			for(int i = 0; i < 4; i++) {
				int nextX = now.x + dx[i];
				int nextY = now.y + dy[i];
				
				if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M ||
				   visited[nextX][nextY] == true || map[nextX][nextY] != 1) {
					continue;
				}
				
				// 큐에 담는다
				q.offer(new Node(nextX, nextY));
				// 방문처리
				visited[nextX][nextY] = true;
			}
		}
		return cnt;
	}
	
	// main
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visited = new boolean[N][M];
		int maxVal = 0;
		int mapCnt = 0;
		
		for(int i=0;i<N;i++) {
			// 맵 한줄씩 입력
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(visited[i][j] == false && map[i][j] == 1) {
					mapCnt++;
					maxVal = Math.max(maxVal, BFS(i, j));
				}
			}
		}
		// 출력		
		System.out.println(mapCnt);
		System.out.println(maxVal);
	}
}

 

---

※ 결과 (백준 1926 그림)

 

---

 

※ 생각정리

처음 그림 문제를 봤을 때 간단히 해결될 거 같다는 생각을 했지만 풀고나서 실행시간이 길어서 놀랐다. 맵 좌표 (0, 0) 부터 시작하여 좌표(N, M)까지 반복문을 실행하며, 방문을 아직안한 좌표이면서 맵에 저장된 값이 1일때 BFS 알고리즘을 실행한다.

BFS내부에서는 상하좌우로 탐색하는데 배열의 범위를 벗어나지 않으면서, 방문하지 않았고, 맵에 저장된 값이 1인 좌표만 큐에 담는다. 큐가 완전히 비어질때까지 해당 과정을 반복한다.

그림의 개수는 처음 BFS알고리즘을 실행한 횟수가 될 수 있고, 가장 큰 그림은 Math.max 함수를 이용해 값을 비교해가며 저장했다.

 

-새벽코딩-