백준 1926번 : 그림 (JAVA) 문제 풀이

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

1926번: 그림

---

BFS의 개념을 가장 잘 이해할 수 있는 문제라고 할 수 있다. 차근차근 한번 풀어보도록 하자.

✏️ 문제

 

🔐 문제 해결

값이 1이면 색칠이 된 부분이니까, 모든 그림을 전부 돌면서 1이거나 방문하지 않은 그림을 체크하면서 처리해주면 될 것 같다.

우선 모든 그림을 2차원 배열에 담아주도록 한다. (StringTokenizer를 이용해서 각각 원소를 넣어준다.)

arr = new int[n][m];

// 배열값 세팅
for(int i=0; i<n; i++){
    st = new StringTokenizer(bf.readLine());
    for(int j=0; j<m; j++){
        arr[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

그럼 이제 모든 배열의 원소들을 순회하면서, 0 이거나 방문한 그림들은 건너뛰어주도록 한다.

그리고, 방문하지 않았거나 1(색칠)인 그림은 큐에 넣어서 연결된 그림을 찾도록 할건데, 이때 중요한 점은 큐(Queue)를 이용하여 연결된 그림을 찾게 할 것이다. 어떻게 하느냐.. 큐에 먼저 넣었던 원소는 해당 그림의 첫번째 시작점이 되는 것이다. 

그렇다면, 첫번째 시작점을 가지고 위, 아래, 오른쪽, 왼쪽을 찾아서 1인 그림을 또 큐에 담고, 다시 큐에서 꺼내서 똑같이 반복하면 끝이다.

 

먼저 큐에 좌표를 넣어주기 위해서 Pair라는 클래스를 생성하여 넣어주도록 한다. 

public class Pair {
	int x, y;
    
    public Pair(int x, int y){
    	this.x = x;
        this.y = y;
    }
    
    public void getX(){
    	return x;
    }
    
    public void getY(){
    	return y;
    }
    
    public int setX(int x){
    	this.x = x;
    }
    
    public int setY(int y){
    	this.y = y;
    }
}

 

이제 큐를 이용해서 BFS를 구현해볼 것이다. 그리 어렵지 않으니 아래 코드를 참고하면서 구현해보자.

// 순서대로, 오른쪽, 아래, 왼쪽, 위쪽 좌표를 계산할 수 있다.
int[] dx = {1, 0 , -1, 0);
int[] dy = {0, -1, 0, 1};

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
    	if (arr[i][j] == 0 || visit[i][j]) {
        	continue;	// 색칠이 안됐거나, 방문했을 때 PASS!
        }
        
        visit[i][j] = true;	// 방문 처리!
        qu.offer(new Pair(i, j));	// 해당 좌표를 넣어준다.
        count++;
        area = 0;
        
        while(!qu.isEmpty()) {
            Pair p = qu.poll();
            area++;
            
            for(int k = 0; k < 4; k++) {
            	int n_X = p.x + dx[k];
                int n_Y = p.y + dy[k];
                
                // 새로 계산한 좌표가 0보다 작거나, 벽에 부딪힌다면 PASS!
                if(n_X < 0 || n_X >= n || n_Y < 0 || n_Y >= m){
                	continue;
                }
                
                if(arr[n_X][x_Y] == 1 && visit[n_X][n_Y]){
                	qu.offer(new Pair(n_X, n_Y));
                    visit[n_X][n_Y] = true;
                }
            }
        }
        if (max > area) {
        	max = area;	// 최대인 그림을 찾는다.
        }
    }
}

여기서 가장 중요한 점은, 새로운 좌표를 계산할 때 벽에 부딪히거나, 그림의 길이에 벗어나면 PASS해줘야 한다!

그리구 마지막에는 그림의 넓이가 최대인 것을 찾아서 max 변수에 담아주면 된다!

 

📝 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] arr;
    static boolean[][] visit;
    static int[] dx;
    static int[] dy;
    static Queue<Pair> qu;

    public static void main(String args[]) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        arr = new int[n][m];
        visit = new boolean[n][m];
        qu = new LinkedList<>();
        
        dx = new int[]{1, 0, -1, 0};
        dy = new int[]{0, 1, 0, -1};
        
        // 배열값 세팅
        for(int i=0; i<n; i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 시작!
        int count = 0;
        int area = 0;
        int max = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                // 0이거나 방문한적이 있으면 생략.
                if(arr[i][j] == 0 || visit[i][j]){
                    continue;
                }
                count++;    // 1이고, 방문을 하지 않았으므로 시작점이 되니까 +1
                qu.offer(new Pair(i, j));   // 큐에 좌표를 넣어준다.
                visit[i][j] = true;     // 방문처리!
                area = 0;    // 0이면 그림이 끊겼으므로 area = 0!
                while(!qu.isEmpty()){
                    Pair p = qu.poll();
                    area++; // 넓이 +1
                    for(int k = 0; k < 4; k++){
                        int n_x = p.x + dx[k];
                        int n_y = p.y + dy[k];
                        if(n_x < 0 || n_x >= n || n_y < 0 || n_y >= m){
                            continue;
                        }
                        if(arr[n_x][n_y] == 1 && !visit[n_x][n_y]){
                            qu.offer(new Pair(n_x, n_y));
                            visit[n_x][n_y] = true;
                        }
                    }
                }
                if(area > max){
                    max = area;
                }
            }
            
        }
        System.out.println(count);
        System.out.println(max);
    }
    
    public static class Pair{
        int x;
        int y;
        
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public int getX(){
            return x;
        }
        public int getY(){
            return y;
        }
        public void setX(int x){
            this.x = x;
        }
        public void setY(int y){
            this.y = y;
        }
        
    }
}