-
[백준] 4963 섬의 개수 - Java알고리즘 문제 풀이 2024. 6. 2. 15:48
문제 - 섬의 개수
https://www.acmicpc.net/problem/4963
접근 방법
이 문제도 그래프 완전 탐색이다 즉, bfs와 dfs로 풀 수 있는 문제이다
하지만 이 문제가 다른 점은 대각선에 있는 것도 탐색을 해야 한다는 것이다
이 부분만 잘 구현 하면 될 것 같다
코드 작성
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int M; static int[][] map; static boolean[][] visited; static int[] dx = {0, -1, 0, 1, -1, 1, -1, 1}; static int[] dy = {1, 0, -1, 0, 1, 1, -1, -1}; static int count; public static void main(String[] args) throws IOException { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { StringTokenizer st; String str = ""; StringBuilder sb = new StringBuilder(); while (!(str = br.readLine()).equals("0 0")) { st = new StringTokenizer(str); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new int[M][N]; visited = new boolean[M][N]; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { map[i][j] = Integer.parseInt(st.nextToken()); } } int count = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (!visited[i][j] && map[i][j] == 1) { count++; dfs(i, j); } } } sb.append(count).append("\n"); } System.out.println(sb); } } public static void dfs(int x, int y) { visited[x][y] = true; for (int i = 0; i < 8; i++) { int ix = dx[i] + x; int iy = dy[i] + y; if (ix >= 0 && ix < M && iy >= 0 && iy < N) { if (!visited[ix][iy] && map[ix][iy] == 1) { dfs(ix, iy); } } } } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 1644 소수의 연속합 - Java (0) 2024.06.16 [백준] 2644 촌수계산 - Java (0) 2024.06.03 [백준] 1012 유기농 배추 - Java (0) 2024.05.30 [프로그래머스] 네트워크 - Java (0) 2024.05.30 [백준] 15670 N과 M(2) - Java (0) 2024.05.29