[백준] 그림 1926번

문제 힌트

1. BFS 방법으로 풀기
   • 큐(Queue)를 이용하여 그림을 찾습니다.
   • (i, j) 위치에서 그림을 찾기 시작하여, 상하좌우 인접한 1들을 큐에 넣고 방문 처리합니다.
   • 큐가 비어질 때까지 반복하며 그림의 크기를 계산합니다.
2. DFS 방법으로 풀기
   • 스택(Stack)을 이용하거나 재귀 호출을 통해 그림을 찾습니다.
   • (i, j) 위치에서 그림을 찾기 시작하여, 상하좌우 인접한 1들을 스택에 넣고 방문 처리합니다.
   • 스택이 비어질 때까지 반복하며 그림의 크기를 계산합니다.
3. 방문 유무 파악하기
   • 도화지와 같은 크기의 boolean[][] 배열을 사용하여 true, false를 이용하면 쉽게 구할 수 있습니다.

BFS와 DFS로 해결하는 방법

BFS로 해결하는 방법

1. 도화지를 탐색하면서 방문하지 않은 1을 찾습니다.
2. 찾으면 큐를 사용하여 BFS를 시작합니다.
3. 큐에서 좌표를 꺼내고 해당 좌표의 상하좌우를 확인하여 조건에 맞으면 큐에 추가합니다.
4. BFS가 종료되면 그림의 크기를 리스트에 저장합니다.
5. 리스트의 크기는 그림의 수, 리스트의 최댓값은 가장 큰 그림의 크기입니다.

DFS로 해결하는 방법

1. 도화지를 탐색하면서 방문하지 않은 1을 찾습니다.
2. 찾으면 스택을 사용하거나 재귀 호출로 DFS를 시작합니다.
3. 스택에서 좌표를 꺼내고 해당 좌표의 상하좌우를 확인하여 조건에 맞으면 스택에 추가합니다.
4. DFS가 종료되면 그림의 크기를 리스트에 저장합니다.
5. 리스트의 크기는 그림의 수, 리스트의 최댓값은 가장 큰 그림의 크기입니다.

 

---

정답은 더보기 클릭

 

BFS 정답

BFS(주석)

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

public class Main {
    // 도화지 크기 n, m
    // 2차원 배열을 생성하고 도화지 크기를 넘지 않는지 확인하는 변수
    static int n, m;
    
    // 도화지, 방문 유무
    static int[][] drawingPaper;
    static boolean[][] visited;
    
    // 그림의 크기
    static int size;
    
    // 좌표 이동 변수 (상하좌우)
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    
    public static void main(String[] args) throws Exception{
        // 입력을 효율적으로 받기 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 효율적으로 하기 위해 BufferedWriter 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 결과를 저장할 리스트 (그림의 크기)
        List<Integer> result = new ArrayList<>();
        
        // 도화지 크기 입력 받기
        String[] area = br.readLine().split(" ");
        n = Integer.parseInt(area[0]);
        m = Integer.parseInt(area[1]);
        
        // 도화지와 방문 유무 배열 초기화
        drawingPaper = new int[n][m];
        visited = new boolean[n][m];
        
        // 도화지 채우는 2중 for문
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                drawingPaper[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        // Main 로직: 그림 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                size = 0;
                if (drawingPaper[i][j] == 1 && !visited[i][j]) {
                    size = 1;
                    bfs(i, j);
                    result.add(size);
                }
            }
        }
        
        // 결과 출력: 그림의 수와 가장 큰 그림의 크기
        if (result.size() == 0) {
            bw.write(0 + "\n");
            bw.write(0 + "\n");
        } else {
            Collections.sort(result);
            bw.write(result.size() + "\n");
            bw.write(result.get(result.size() - 1) + "\n");
        }
        
        bw.flush();
        bw.close();
    }
    
    /**
     * BFS를 이용해 그림의 크기를 계산하는 메서드
     */
    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[] indexArr = queue.poll();
            // 현재 큐에서 추출한 x, y 좌표
            int nowX = indexArr[0];
            int nowY = indexArr[1];
            
            // 상하좌우 이동하여 조건에 맞으면 queue에 넣기
            for (int i = 0; i < 4; i++) {
                int nx = nowX + dx[i];
                int ny = nowY + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && drawingPaper[nx][ny] == 1) {
                    // 그림 사이즈 + 1, 방문 표시, 큐에 추가하여 해당 좌표의 상하좌우 확인
                    size++;
                    visited[nx][ny] = true;
                    queue.add(new int[] {nx, ny});
                }
            }
        }
    }
}

 

BFS(주석 제거)

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

public class Main {
    static int n, m;
    
    static int[][] drawingPaper;
    static boolean[][] visited;
    
    static int size;
    
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        List<Integer> result = new ArrayList<>();
        
        String[] area = br.readLine().split(" ");
        n = Integer.parseInt(area[0]);
        m = Integer.parseInt(area[1]);
        
        drawingPaper = new int[n][m];
        visited = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                drawingPaper[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                size = 0;
                if (drawingPaper[i][j] == 1 && !visited[i][j]) {
                    size = 1;
                    bfs(i, j);
                    result.add(size);
                }
            }
        }

        if (result.size() == 0) {
            bw.write(0 + "\n");
            bw.write(0 + "\n");
        } else {
            Collections.sort(result);
            bw.write(result.size() + "\n");
            bw.write(result.get(result.size() - 1) + "\n");
        }
        
        bw.flush();
        bw.close();
    }

    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[] indexArr = queue.poll();
            int nowX = indexArr[0];
            int nowY = indexArr[1];
            
            for (int i = 0; i < 4; i++) {
                int nx = nowX + dx[i];
                int ny = nowY + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && drawingPaper[nx][ny] == 1) {
                    size++;
                    visited[nx][ny] = true;
                    queue.add(new int[] {nx, ny});
                }
            }
        }
    }
}

DFS 정답

DFS

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

public class Main {
    // 도화지의 크기 (행과 열의 개수)
    static int n, m;
    // 도화지 배열과 방문 여부를 확인하는 배열
    static int[][] drawingPaper;
    static boolean[][] visited;
    // 현재 그림의 크기
    static int size;
    // 상하좌우 이동을 위한 델타 배열
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception {
        // 입력을 받기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 위한 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 결과를 저장할 리스트 (그림의 크기)
        List<Integer> result = new ArrayList<>();

        // 도화지의 크기 입력 받기
        String[] area = br.readLine().split(" ");
        n = Integer.parseInt(area[0]);
        m = Integer.parseInt(area[1]);

        // 도화지와 방문 유무 배열 초기화
        drawingPaper = new int[n][m];
        visited = new boolean[n][m];

        // 도화지 배열을 입력 받기
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                drawingPaper[i][j] = Integer.parseInt(line[j]);
            }
        }

        // 도화지를 탐색하여 그림을 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 그림의 크기를 초기화
                size = 0;
                // 해당 위치가 1이고 방문하지 않았다면 DFS 실행
                if (drawingPaper[i][j] == 1 && !visited[i][j]) {
                    size = 1;
                    dfs(i, j);
                    // 그림의 크기를 결과 리스트에 추가
                    result.add(size);
                }
            }
        }

        // 결과 출력: 그림의 수와 가장 큰 그림의 크기
        if (result.size() == 0) {
            bw.write(0 + "\n");
            bw.write(0 + "\n");
        } else {
            Collections.sort(result);
            bw.write(result.size() + "\n");
            bw.write(result.get(result.size() - 1) + "\n");
        }

        bw.flush();
        bw.close();
    }

    // DFS를 이용해 그림의 크기를 계산하는 메서드
    static void dfs(int x, int y) {
        // 현재 위치를 방문한 것으로 표시
        visited[x][y] = true;
        // 상하좌우를 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 유효한 위치인지, 방문하지 않았는지, 그림의 일부분인지 확인
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && drawingPaper[nx][ny] == 1) {
                // 그림의 크기 증가
                size++;
                // 재귀적으로 DFS 실행
                dfs(nx, ny);
            }
        }
    }
}

 

DFS(주석제거)

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Integer> result = new ArrayList<>();

        String[] area = br.readLine().split(" ");
        n = Integer.parseInt(area[0]);
        m = Integer.parseInt(area[1]);

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

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                drawingPaper[i][j] = Integer.parseInt(line[j]);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                size = 0;
                if (drawingPaper[i][j] == 1 && !visited[i][j]) {
                    size = 1;
                    dfs(i, j);
                    result.add(size);
                }
            }
        }

        if (result.size() == 0) {
            bw.write(0 + "\n");
            bw.write(0 + "\n");
        } else {
            Collections.sort(result);
            bw.write(result.size() + "\n");
            bw.write(result.get(result.size() - 1) + "\n");
        }

        bw.flush();
        bw.close();
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && drawingPaper[nx][ny] == 1) {
                size++;
                dfs(nx, ny);
            }
        }
    }
}