Baekjoon[2468] - 안전 영역

링크

 

2468번: 안전 영역

문제설명

• 인접 영역 탐색

문제풀이

• 인접 영역 탐색 -> BFS

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main123 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/2468.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int ans=0;
        int temp=0;
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        boolean[][] visit = new boolean[N][N];
        int max_height=0;

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


        int near_height=0;
        int[] now;
        int nr;
        int nc;
        for (int i = 0; i < max_height; i++) {
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if(map[r][c]>i) {
                        visit[r][c]=true;    //방문가능
                    }
                    else {
                        visit[r][c]=false;
                    }
                }
            }
            temp=0;
            LinkedList<int[]> q = new LinkedList<>();
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
//                    방문가능
                    if(visit[r][c]) {
                        q.add(new int[] {r,c});
                        visit[r][c]=false;    //방문함
                        while(!q.isEmpty()) {
                            now=q.poll();
                            for (int d = 0; d < 4; d++) {
                                nr= now[0] + dir[d][0];
                                nc= now[1] + dir[d][1];
                                if(nr>=0 && nr<N && nc>=0 && nc<N && visit[nr][nc]) {
                                    q.add(new int[] {nr,nc});
                                    visit[nr][nc]=false;
                                }
                            }
                        }
                        temp++;
                    }
                }
            }
            ans = Math.max(ans, temp);
        }
        System.out.println(ans);
    }
}

아쉬운점

• 문제 이해 못했음
  • 살아있는 애들 중 상하좌우중 최대값이 안전영역인줄알았음
  • 그냥 붙어있는 영역이 안전영역임

잘한점

• 최대값 구해서 그만큼만 계산

그래프 탐색 효율성

• 그래프의 연결성 확인
  • DFS가 메모리 차원에서 유리 - 더빠름
  • BFS는 queue 사용
• 그래프의 거리 확인
  • DFS가 유리?