알고리즘 스터디 -bfs

1926

• 알고리즘 : bfs
• 난이도 : 실버1

문제

1926

접근

• 각 그림을 접근 하는 것은 dfs와 bfs로 구현한다.
  • 이번 문제는 bfs로 접근하였다.

풀어보기

package org.example;

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

public class Main {
	static int n;
	static int m;
	static int[][] whiteBoard;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int paintCount;
	static int largestPaint;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] temp = br.readLine().split(" ");
		n = Integer.parseInt(temp[0]);
		m = Integer.parseInt(temp[1]);

		whiteBoard = new int[n][m];
		visited = new boolean[n][m];

		for(int i = 0; i < n; i++) {
			String[] board = br.readLine().split(" ");
			for(int j = 0; j < m; j++) {
				whiteBoard[i][j] = Integer.parseInt(board[j]);
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if (!visited[i][j] && whiteBoard[i][j] == 1) {  // 방문하지 않았고 그림인 경우만 BFS 실행
					bfs(i, j);
				}
			}
		}
		System.out.println(paintCount);
		System.out.println(largestPaint);
	}
	public static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[]{x, y});
		visited[x][y] = true;  // 시작점을 방문 처리

		int size = 1;
		while(!queue.isEmpty()) {
			int[] curr = queue.poll();
			int currX = curr[0];
			int currY = curr[1];

			for(int i =0; i < 4; i++) {
				int nextX = currX + dx[i];
				int nextY = currY + dy[i];
				if(nextX >= 0 && nextY >= 0 && nextX < n && nextY < m && !visited[nextX][nextY] && whiteBoard[nextX][nextY] == 1) {
					visited[nextX][nextY] = true;
					queue.add(new int[]{nextX, nextY});
					size++;
				}
			}
		}
		largestPaint = Math.max(largestPaint, size);
		paintCount++;

	}

}

시행착오

• size를 0으로 시작하여 시작 지점의 갯수를 카운트 하지 않았다.
• main 함수에서 방문했던 노드와 1이 아닌 노드를 제외하고 방문해야하는데 모든 노드를 방문하도록 하였다.
• 가장 큰 그림을 구할 때 while문이 끝나고 한번에 했어도 관계 없었다.
  어차피 1로 이루어진 붙어있는 노드만 방문하기에 가능하다.
• painCount도 while문이 끝나고 같이 증가시킨다.