lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이 문제는 너비 우선 탐색인 BFS를 통해 쉽게 풀 수 있다.


아이디어 도출

문제에서 요구하는 총 그림의 개수와 모든 그림 중 가장 큰 넓이를 구하면 된다. 이를 위해 생각한 아이디어는 다음과 같다.

  1. 입력받은 도화지 배열에서 색칠된 노드를 탐색하는데, BFS를 통해 상,하,좌,우로 탐색하며 연결된 그림을 찾는다.
  2. 이때, 새로운 그림을 찾을 떄마다 카운트하면 총 그림의 개수를 구할 수 있다.
  3. 하나의 그림에서 연결된 그림 노드를 찾을 때, 노드 위치에 +1씩 저장하여 그림의 넓이를 저장해놓는다.
  4. 그림마다 구한 넓이를 비교해가며 총 그림 중 가장 큰 넓이를 구할 수 있다,


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

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

class Main {    
    // 입력 N, M 선언
    static int N;
    static int M;

    // 상하좌우를 탐색하기 위한 dx, dy 배열 선언
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    // 방문 배열 선언
    static boolean[][] visited;

    // 입력 도화지 배열 선언
    static int[][] arr;

    // 그림의 총 개수를 구할 cnt, 그림별 넓이를 구할 area, 모든 그림 중 가장 큰 넓이를 가질 max 변수 선언
    static int cnt;
    static int area;
    static int max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 방문 배열 및 도화지 배열 초기화
        visited = new boolean[N][M];
        arr = new int[N][M];

        // 입력값을 통해 도화지 배열 갱신
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 구할 그람의 개수와 가장 큰 그림의 넓이를 구하기 위해 cnt, area 초기화
        cnt = 0;

        // 도화지 배열을 돌며 그림의 개수를 찾기 위한 BFS 함수를 호출한다.
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(!visited[i][j]) {
                    if(arr[i][j] != 0) {
                        // 그림별 넓이를 계산하기 위한 area 초기화
                        area = 1;
                        // BFS 호출하여 i, j 위치부터 순회
                        BFS(i, j);
                        // 그림별 area를 비교하여 가장 더 큰 넓이를 max에 저장
                        max = Math.max(area, max);
                    }
                }
            }
        }

        bw.write(cnt+"\n");
        bw.write(max+"\n");

        bw.close();
        br.close();
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        // 그림의 개수 카운트
        cnt++;
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<4; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(0<=i && 0<=j && i<N && j<M) {
                    if(!visited[i][j] && arr[i][j] != 0) {
                        visited[i][j] = true;
                        // 그릴마다 연결노드의 넓이를 저장
                        area++;
                        arr[i][j] = area;
                        q.add(new int[]{i, j});
                    }
                }
            }
        }        
    }
}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy