백준 1926 그림 자바 풀이

난이도 : 실버1

풀이일 : 12177

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

1926번: 그림

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

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

public class J17_b_1926 {
	static int N, M;
	static int[][] paper;
	static boolean[][] visited;
	static int num; // 그림 크기
    	// 이동 좌표
	static int[] di = {-1, 1, 0, 0};
	static int[] dj = {0, 0, -1, 1};
	
	static void BFS(int x, int y) {
		visited[x][y] = true;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[]{x, y});
		
		while (!queue.isEmpty()) {
			int[] temp = queue.poll();
			int i = temp[0];
			int j = temp[1];
			
			for (int k = 0; k < 4; k++) {
				int ni = i + di[k];
				int nj = j + dj[k];
				
				if (ni >= 0 && ni < N && nj >= 0 && nj < M) {
					if (paper[ni][nj] == 1 && !visited[ni][nj]) {
						num++;
						visited[ni][nj] = true;
						queue.add(new int[] {ni, nj});
					}
				}
			}
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer a = new StringTokenizer(br.readLine());
		
		boolean flag = true; // 그림이 없는 경우 판별
		List<Integer> result = new ArrayList<>();
		int maxi = 0;
		N = Integer.parseInt(a.nextToken());
		M = Integer.parseInt(a.nextToken());
		
		paper = new int[N][M];
		visited = new boolean[N][M];
		
		// 입력 받기
		for (int i = 0; i < N; i++) {
			StringTokenizer b = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				paper[i][j] = Integer.parseInt(b.nextToken());
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (paper[i][j] == 1 && !visited[i][j]) {
					flag = false;
					num = 1;
					BFS(i, j);
					result.add(num);
				}
			}
		}
		
        	// 가장 큰 그림의 크기 찾기
		for (int i = 0; i < result.size(); i++) {
			if (result.get(i) > maxi) {
				maxi = result.get(i);
			}
		}
		
        	// 그림의 수와 가장 큰 그림의 크기 출력
		if (flag) {
			System.out.println(0);
			System.out.println(0);
		}
		else {
			System.out.println(result.size());
			System.out.println(maxi);
		}
	}
}

• 배운 것
  • queue.poll : queue에서 가장 앞 요소 반환
  • result.get(i) : List<Integer>에서 i 번째 요소에 접근하는 방법
• 풀이
  • 이차원 배열을 입력 받아 저장한 후, 순회하며 그림이 그려진 곳을 찾기
  • 찾은 위치부터 그림의 크기를 bfs로 구하기
  • 각 그림의 크기를 result에 저장하기
  • 그림의 총 개수와 가장 큰 그림의 크기 출력

---

느낀점

• 이제 조금 자바 알고리즘 기초에 익숙해지고 있는 느낌이다. 로직적인 고민이 아니라 자바라서 파이썬과 달라서 모르는 부분은 빠르게 검색해서 해결하고 익숙해지자.