[백준/java] 1926번: 그림 - BFS(Breath-First-Search)

백준 1926번: 그림

 

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

1926번: 그림

 

※ 변수 설명

 (1) board : 그림판을 나타내는 2차원 배열. 0과 1로 구성되어있으며, 1로 연결된 구역이 하나의 그림이다

 (2) visit : board 2차원 배열 순회 시 방문 여부를 나타내는 2차원 배열.

 (3) dx, dy : Spot 객체의 위치를 기준으로 상(0, 1), 하(0, -1), 좌 (-1, 0), 우(1, 0)의 0과 1, 방문여부를 파악하기 위한 방향 배열

 (4) N : 그림판의 행의 갯수

 (5) M : 그림판의 열의 갯수

 (6) cnt : 그림의 갯수

 (7) max : 그림의 크기 중 가장 큰 값

 

반응형

※ 동작 방식

 (1) 이중 for문을 순회하면서 현재의 위치가 0인지 1인지, 방문했던곳인지 아닌지 체크

 (2) 미방문 위치면 그림의 갯수를 증가하고, 방문 표시를 한다.

 (3) 큐를 생성하여 현재 위치를 큐에 넣는다

 (4) 큐가 비어있는지의 여부를 묻는 while문을 순회한다.

 (5) 큐에서 위치를 꺼낸다

 (6) 꺼낸 위치의 상, 하, 좌, 우의 위치의 방문 여부, 0과 1의 값을 확인한다

 (7) 방문하지 않았고 값이 1인 곳이면 방문표시를 하고 큐에 넣고 다음 방향 확인 진행한다.

 (8) 1에 해당되는 위치가 있으면 그림의 넓이를 증가시킨다

 (8) 현재 Spot의 상, 하, 좌, 우의 그림 여부를 파악하고 난 후 max값을 비교하여 max값을 결정한다.

 

728x90

 

package bfs;

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

public class Picture {
	static int[][] board = new int[501][501];
	static boolean[][] visit = new boolean[501][501];
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int N, M, cnt, max;
	
	static class Spot {
		int x, y;
		
		public Spot(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	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());
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs();
		System.out.println(cnt + "\n" + max);
		
	}
	
	public static void bfs() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				
				if(board[i][j] == 0 || visit[i][j]) continue;
				cnt++;
				visit[i][j] = true;
				
				Queue<Spot> q = new LinkedList<Spot>();
				q.add(new Spot(i, j));
				
				int area = 0;
				
				while(!q.isEmpty()) {
					area++;
					Spot cur = q.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(visit[nx][ny] || board[nx][ny] == 0) continue;
						visit[nx][ny] = true;
						q.add(new Spot(nx, ny));
					}
					
					max = Math.max(max, area);
				}
				
			}
		}
	}
}