Park DJ
dj0998
Park DJ
전체 방문자
오늘
어제
  • 분류 전체보기 (363)
    • 백준 (363)

공지사항

인기 글

태그

  • 백준 1747
  • 백준 12605
  • 백준 24039
  • 백준 15961
  • 백준 15655
  • 백준 6550
  • 백준 10709
  • 백준 8892
  • 백준 2343
  • 백준 1011
  • 백준 3049
  • 백준
  • 백준 15312
  • 백준 3135
  • 백준 2225
  • Java
  • 백준 12871
  • 자바
  • 백준 1531
  • 백준 7662
  • 백준 2467
  • 백준 14582
  • 백준 1495
  • 백준 16194
  • 백준 4659
  • 백준 7567
  • 백준 2591
  • 백준 1064
  • 백준 1914
  • 백준 16926
hELLO · Designed By 정상우.
Park DJ

dj0998

백준 4963 섬의 개수(Java)
백준

백준 4963 섬의 개수(Java)

2023. 2. 7. 12:46

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net


 

해석 및 팁

 


 

이 문제는 dfs를 활용하면 되는 문제입니다. 다만 주의할 점은 확인해야 하는 범위가 상하좌우가 아닌 대각선이 포함된다는 점입니다,

 


 

Java 코드

 


import java.util.Scanner;

public class Main {

  static int w;
  static int h;
  static int[][] arr;
  static boolean[][] visit;
  static int[] lr = {0, 0, -1, 1, -1, -1 , 1, 1};
  static int[] up = {1, -1, 0, 0, 1, -1 , 1, -1};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
   
    while(true) {
      int count = 0;
      arr = new int[51][51];
      visit = new boolean[51][51];
      w = sc.nextInt();
      h = sc.nextInt();
      if(w == 0 && h == 0) break;
      
      for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) arr[i][j] = sc.nextInt();
      }

      for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
          if(arr[i][j] == 1 && visit[i][j] == false) {
            dfs(i, j);
            count++;
          }
        }
      }
      sb.append(count+"\n");
    }
    
    System.out.println(sb);
  }

  public static void dfs(int a, int b) {
    visit[a][b] = true;
    for(int i = 0; i < 8; i++) {
      int x = a + lr[i];
      int y = b + up[i];
      if(x > 0 && y > 0 && x <= h && y <= w && arr[x][y] == 1 && visit[x][y] == false) dfs(x, y);
    }
  }

}

'백준' 카테고리의 다른 글

백준 1182 부분수열의 합(Java)  (0) 2023.02.07
백준 10799 쇠막대기(Java)  (0) 2023.02.07
백준 11279 최대 힙(Java)  (0) 2023.02.07
백준 14889 스타트와 링크(Java)  (0) 2023.02.07
백준 1654 랜선 자르기(Java)  (0) 2023.02.06
    '백준' 카테고리의 다른 글
    • 백준 1182 부분수열의 합(Java)
    • 백준 10799 쇠막대기(Java)
    • 백준 11279 최대 힙(Java)
    • 백준 14889 스타트와 링크(Java)
    Park DJ
    Park DJ

    티스토리툴바