[백준] 2468 : 안전영역 [JAVA] 실버1

백준

 

문제 풀이 설명 (summary)

• 2차 배열에 주어진 조건으로 맵 구성
• 방향에 따라 queue 에 추가하고 방문한 위치는 방문 여부 체크
• 안전 영역의 개수를 구하는 문제 
• 모든 위치에서 시작해서 종료될 때마다 카운트
• 최종 카운트 출력

 

문제 풀이 접근법

• 너비우선 탐색 (BFS) 
• 삽입 (add) / 삭제 (poll) : 먼저 들어온 데이터가 먼저 나가는 구조
• FIFO (First In, First Out)

 

풀이 코드 (Code)

public class Main {

    static boolean[][] visited;
    static int size;
    static int[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static List<Integer> result = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());

        map = new int[size][size];
        visited = new boolean[size][size];
        int maxHeight = 0;

        for (int i = 0; i < size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                int nowCnt = Integer.parseInt(st.nextToken());
                map[i][j] = nowCnt;
                maxHeight = Math.max(nowCnt, maxHeight);
            }
        }
        for (int i = 1; i <= maxHeight; i++) {

            int count = 0;
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {

                    if(!visited[j][k] && map[j][k] > i) {
                        bfs(j, k, i);
                        count += 1;
                    }
                }
            }
            result.add(count);

            visited = new boolean[size][size];

        }

        for (Integer i : result) {
            System.out.println("i = " + i);
        }
        System.out.println(Collections.max(result));
    }

    static int bfs(int y, int x, int height) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();

        queue.add(new int[]{y,x});
        visited[y][x] = true;
        int maxCount = 1;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currY = curr[0];
            int currX = curr[1];

            for (int i = 0; i < 4; i++) {
                int ny = currY + dy[i];
                int nx = currX + dx[i];

                if (nx >= 0 && ny >= 0 && nx < size && ny < size) {
                    if(!visited[ny][nx] && map[ny][nx] > height) {
                        queue.add(new int[]{ny, nx});
                        visited[ny][nx] = true;
                    }
                }
            }
        }


        return maxCount;
    }
}

 

문제 링크 (Link)

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