[BAEKJOON]1926 그림

문제 요약

• 알고리즘 분류: bfs, 구현, 시물레이션
• 난이도:Silver1
• 문제내용:
  • 가로, 세로 크기가 n, m인 도화지가 있다.
  • 그림영역과 빈 영역이 있는데 그림 영역 개수와 가장 큰 그림을 출력해라.
• 사이트: https://www.acmicpc.net/problem/1926

1926번: 그림

 

문제풀이

 이번 문제는 DFS,BFS 탐색 문제이다. DFS로 풀수있지만 BFS가 DFS보다 속도가 더 빨라서 이번 문제는 BFS로 푸는게 좋다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 2차원 배열로 변경 된것만 생각하면 된다.

문제 접근 방법

 이번 문제의 핵심는 BFS + 시물레이션 2개를 구현 해야 한다. 일단 시물레이션은 어떻게 구현 해야 하는지 부터 봐야 한다. 일단 (0, 0) 부터 시작해서 (N, M)까지 탐색하면서 채워진 곳을 찾는다. 채워진 곳을 찾았으면 채워진 곳 부터 시작해서 상하좌우로 채워진 곳을 찾고 찾은 영역을 빈 영역으로 바꿔 버리면 된다.

 채워 진곳을 다 찾았으면 영역개수를 저장하고 그 다음 채워진곳을 찾으면 된다. 도화지 탐색 이 다끝났으면 영역개수와 가장 큰 영역을 출력하면된다.

정리

1. (0, 0)부터 (M, M)까지 탐색을 하면서 채워진 영역을 구한다.
2. 빈 영역을 구했으면 bfs 알고리즘으로 상하좌우 탐색하면서 채워진 영역을 빈영역으로 변경하고 채워진 개수만큼 추가한다.

Code

python

import sys
from collections import deque
input = sys.stdin.readline

# 상하좌우 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 그림 탐색
def bfs(x, y):
    queue = deque([(x, y)])
    picture[x][y] = 0
    count = 1
    while queue:
        nx, ny = queue.popleft()
        for k in range(4):
            fx, fy = nx + dx[k], ny + dy[k]
            # 그림 영역이 포함 되어 있는지 확인
            if 0 <= fx < n and 0 <= fy < m and picture[fx][fy] == 1:
                # 그림 역역있으면 영역을 지우고 면적개수 +1 증가한다.
                picture[fx][fy] = 0
                count += 1
                queue.append((fx, fy))

    counter.append(count)

n, m = map(int, input().split())
picture = [list(map(int, input().split())) for _ in range(n)]
counter = [0] # 없는 경우 0을 출력 해야 하기 때문에 0을 추가한다.

# 그림 전체 탐
for i in range(n):
    for j in range(m):
        if picture[i][j] == 1:
            bfs(i, j)

print(len(counter) - 1)
print(max(counter))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	
	static int n, m;
	static int[][] picture;
	static List<Integer> counter = new ArrayList<Integer>(); // 영역 넓이 담을 공간
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		picture = new int[n][m];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++){
				picture[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		counter.add(0); // 없는 경우 0을 출력 해야 하기 때문에 0을 추가한다.
		 
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++){
				if(picture[i][j] == 1) bfs(i, j);
			}
		}
		
		System.out.println(counter.size() - 1);
		System.out.println(Collections.max(counter));
	}
	
	public static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {x, y});
		int count = 1;
		int[] dx = {0, 0, -1, 1};
		int[] dy = {-1, 1, 0, 0};
		picture[x][y] = 0;
		while (!queue.isEmpty()) {
			int[] location = queue.poll();
			int nx = location[0];
			int ny = location[1];
			
			for(int i = 0; i < 4; i++) {
				int fx = nx + dx[i];
				int fy = ny + dy[i];
				// 그림 영역이 포함 되어 있는지 확인
				if(0 <= fx && fx < n && 0 <= fy && fy < m && picture[fx][fy] == 1) {
					// 그림 역역있으면 영역을 지우고 면적개수 +1 증가한다.
					count++;
					picture[fx][fy] = 0;
					queue.add(new int[] {fx, fy});
				}
			}
		}
		counter.add(count);
	}
}