[문제풀이] 08-13. 섬나라 아일랜드(BFS)

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0813. 섬나라 아일랜드(BFS)

🗒️ 문제

🎈 나의 풀이

	private static int size;
    private static int[][] world;
    private static int[] dx = {1, 0, -1, 0, 1, -1, 1, -1};
    private static int[] dy = {0, 1, 0, -1, -1, -1, 1, 1};
    private static class Point {
        int x;
        int y;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    private static void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        Q.add(new Point(x, y));

        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Point island = Q.poll();
                world[island.x][island.y] = 0;

                for(int j=0; j<dx.length; j++) {
                    int nx = island.x + dx[j];
                    int ny = island.y + dy[j];
                    if(nx>=0 && nx<size && ny>=0 && ny<size && world[nx][ny]==1)
                        Q.add(new Point(nx, ny));
                }
            }
        }
    }
    private static int solution() {
        int answer = 0;

        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                if(world[i][j] == 1) {
                    BFS(i, j);
                    answer++;
                }
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        world = new int[size][size];

        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) world[i][j] = sc.nextInt();
        }

        System.out.println(solution());

    }

🖍️ 강의 풀이

  class Point{
      int x, y;
      Point(int x, int y){
          this.x=x;
          this.y=y;
      }
  }
  class Main {
      static int answer=0, n;
      static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
      static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
      Queue<Point> queue = new LinkedList<>();
      public void BFS(int x, int y, int[][] board){
          queue.add(new Point(x, y));
          while(!queue.isEmpty()){
              Point pos = queue.poll();
              for(int i=0; i<8; i++){
                  int nx=pos.x+dx[i];
                  int ny=pos.y+dy[i];
                  if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1){
                      board[nx][ny]=0;
                      queue.add(new Point(nx, ny));
                  }
              }		
          }
      }

      public void solution(int[][] board){	
          for(int i=0; i<n; i++){
              for(int j=0; j<n; j++){
                  if(board[i][j]==1){
                      answer++;
                      board[i][j]=0;
                      BFS(i, j, board);
                  }
              }
          }
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          n=kb.nextInt();
          int[][] arr=new int[n][n];
          for(int i=0; i<n; i++){
              for(int j=0; j<n; j++){
                  arr[i][j]=kb.nextInt();
              }
          }
          T.solution(arr);
          System.out.println(answer);
      }
  }

💬 짚어가기

해당 문제를 DFS를 이용하여 풀어보았다. 나의 풀이에서는 지도 전체의 정보를 2차원 배열
world에 보관하였고, 좌표를 보관할 수 있는 클래스 Point를 생성하였다.

지도를 순회하면서 섬(1)이 발견되었을 때 DFS를 수행하여 섬 전체 땅을 찾는 로직이다.

dx와 dy 배열을 두어 좌표에서 상하좌우 그리고 대각 방향의 움직을 보관하였고, BFS에서
발견되는 섬의 위치에는 0을 담아 중복 탐색을 방지하였다.

BFS에서는 인접한 좌표를 탐색하며 지도 영역 내에서 해당 좌표가 섬인지 판별하였고, 섬인 경우
Queue에 보관하고, 다음 큐를 탐색할 때 섬 하나의 전체 영역을 탐색하도록 하였다.

모든 지도 순회를 마쳤을 때 섬의 개수를 반환하여 문제를 해결하였다.
강의에서도 동일한 로직으로 풀이하였다.