[백준/JAVA] 1926번: 그림

🔺 문제

1926번: 그림

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    
    static int n, m;    // 세로, 가로
    
    static int[][] draw;       // 인접 행렬
    static boolean[][] visited; // 방문 배열
    static int group = 0;       // 그룹 수
    static int max = 0;         // 가장 넓은 그림의 넓이
    static int result = 0;      // 매번 bfs 수행할 때마다 나오는 그림 넓이
    
    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());   // 가로
        
        // 변수들 초기화
       draw = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];
        
        // 입력 받기
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= m ; j++) {
               draw[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 각 점에 대해 bfs 수행
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= m ; j++) {
                if(!visited[i][j] && draw[i][j] == 1) {
                    group++;
                    bfs(i, j);
                    max = Math.max(max, result);
                }
            }
        }
        
        System.out.println(group + "\n" + max);
    }
    
    private static void bfs(int a, int b) {
        visited[a][b] = true;
        result = 1;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(1 <= x && x <= n && 1 <= y && y <= m && !visited[x][y] && draw[x][y] == 1) {
                    visited[x][y] = true;
                    queue.add(new int[] {x, y});
                    result++;
                }
            }
        }
    }
}
 

✅ 해결 아이디어
✔ BFS / DFS
- 각 점에 대해 조건을 만족하면 그룹 갯수를 세고, bfs를 수행하면서 그림 면적을 구한다.

 

 

---

🔺 다른 풀이들

- 숏코딩 보니까 DFS로 푸신 분들이 많으셨다.

로그인

 

---

💬 느낀 점

63번째 줄에 조건을 그냥 다 넣어서 조건식을 만들었다.

 

그런데 다른 분들 풀이를 보니

적합하지 않은 조건식을 먼저 작성하고, 이에 대한 결과를 continue;로 해서

필터링하셨다. (참고 : 해당 코드 Line 18-19)

 

나도 다음엔 이렇게 해야겠다!

 

암튼 30분 안에 혼자 풀어서 뿌듯하다! 셀프북박북박...ㅋ

 

1회독	2회독	3회독	4회독	5회독
V