[Java] 백준 1926 (그림) 자바 문제 풀이

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

1926번: 그림

알고리즘 분류

1. 너비우선 탐색
2. 깊이우선 탐색
3. 그래프 탐색

 

풀이

그래프 탐색 문제이다. 저는 너비 우선 탐색(bfs)를 이용해 풀었다.

먼저 초기화 작업이다.

 

 

x 축 좌표로 이동할 int형 배열 dx,

y 축 좌표로 이동할 int형 배열 dy,

그림이 그려져 있는지 안그려져 있는지 (0과 1인지) 을 구분하는 2차원 배열 map,

방문했는지 안했는지 구분하는 boolean형 2차원 배열 visited,

그리고 너비 우선 탐색에 사용할 Queue이다.

private static final int[] dx = {-1, 0, 1, 0};
private static final int[] dy = {0, 1, 0, -1};
private static int[][] map;
private static boolean [][] visited;
private static Queue<int []> queue;

 

 

 

 

입력을 받은 후 for 루프문을 돌면서 그림이 그려져 있거나 ( 값이 1일 때 )

아직 방문하지 않은 노드면 i, y ( x축, y축 ) 를 매개변수로 넣고 bfs메서드를 실행하도록 하였다.

그림 넓이를 반환해서 area에 담은 후 list에 추가 했다.

for (int i = 0; i < map.length; i++) {
    for (int j = 0; j < map[0].length; j++) {
        if(map[i][j] == 1 && !visited[i][j]){
             int area = bfs(i, j);
             list.add(area);
         } // if
     } // for
} // for

 

 

 

 

bfs 메서드 이다.

매개변수로 받은 i, y (x 좌표, y좌표) 값을 큐에 담은 후 방문 처리(visited[][] = true)를 해준다.

그리고 while 루프문을 돌면서 움직일 x 좌표, y좌표를 구한 뒤

그 좌표 들이 0보다 작거나 배열의 크기보다 크면 continue를 하도록 조건문을 추가 하였다.

만약 그림이 그려져 있거나(map[][] == 1) 아직 방문하지 않은 좌표(!visited[][])라면
queue에 그 좌표들을 배열로 넣어 다시 탐색하게 하고 방문처리도 해준다.

그리고 탐색한 그 좌표도 그림이 그려져 있는 곳 이므로 sum += 1 처리를 해줬다. (그림 크기가 1증가한다.)

    public static int bfs(int x, int y){
        queue = new LinkedList<>();
        queue.add(new int[]{x, y}); // 현재 좌표에서 탐색해야 하므로 queue에 넣는다
        visited [x][y] = true; // 방문 처리
        int sum = 1;
        while (!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int i = 0; i < 4; i++) {
                int mx = cx + dx[i]; // 움직일 x 좌표
                int my = cy + dy[i]; // 움직일 y 좌표

                if (mx < 0 || mx >= map.length || my < 0 || my >= map[0].length){
                    continue;
                }

                if(map[mx][my] == 1 && !visited[mx][my]){
                    queue.add(new int[]{mx, my});
                    visited[mx][my] = true;
                    sum++;
                } // if
            } // for

        } // while

        return sum;
    } // bfs

 

 

 

 

 

아래는 전체 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static int[][] map;
    private static boolean [][] visited;
    private static Queue<int []> queue = new LinkedList<>();;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < map.length; i++) {
            String temp[] = br.readLine().split(" ");
            for (int j = 0; j < temp.length; j++) {
                map[i][j] = Integer.parseInt(temp[j]);
            } // for
        } // for

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if(map[i][j] == 1 && !visited[i][j]){
                    int area = bfs(i, j);
                    list.add(area);
                } // if
            } // for
        } // for

        Collections.sort(list);
        System.out.println(list.size());
        if (list.isEmpty() ){
            System.out.println("0");
        }else{
            System.out.println(list.get(list.size()-1));
        }

    } // main

    public static int bfs(int x, int y){
        
        queue.add(new int[]{x, y});
        visited [x][y] = true;
        int sum = 1;
        while (!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int i = 0; i < 4; i++) {
                int mx = cx + dx[i];
                int my = cy + dy[i];

                if (mx < 0 || mx >= map.length || my < 0 || my >= map[0].length){
                    continue;
                }

                if(map[mx][my] == 1 && !visited[mx][my]){
                    queue.add(new int[]{mx, my});
                    visited[mx][my] = true;
                    sum++;
                } // if
            } // for

        } // while

        return sum;
    } // bfs
}