기본적인 그래프 문제, DFS 접근
풀이)
지도에서 현재 섬인 경우 해당 섬의 (위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4방향) 확인.
getDFS(x, y);
if) 해당 방향으로 섬인 경우 재귀탐색으로 다시 확인. // 단, 아직 방문하지 않은 섬인 경우
else) 바다인 경우 return.
--> 함수 return 경우 모든 인접 지역을 방문했거나 바다인경우로 섬+1
map[][] : 배열로 섬과 지도를 나타내는 지도 저장
visit[][] : 이미 방문한 지역 저장 // 1 : 방문, 0 : 미방문
DFS 그래프로 <위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4 방향> 이동
int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1};
int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0};
import java.util.ArrayList; import java.util.Scanner; public class Main { static int w; static int h; static int[][] map; static int[][] visit; static int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1}; static int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0}; static ArrayListar = new ArrayList<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ w = sc.nextInt(); h = sc.nextInt(); if(w == 0 && h == 0){ break; } map = new int[w][h]; visit = new int[w][h]; int landCount =0; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ map[j][i] = sc.nextInt(); } } for(int i=0;i<w;i++){ for(int j=0;j<h;j++){ if(map[i][j] == 1 && visit[i][j] == 0){ getDFS(i, j); landCount++; } } } ar.add(landCount); } for(int i=0;i<ar.size();i++) System.out.println(ar.get(i)); } public static void getDFS(int x, int y){ visit[x][y] = 1; for(int i=0;i<8;i++){ int ax = x+xx[i]; int ay = y+yy[i]; if(ax>=0 && ax<w && ay>=0 && ay<h){ if(map[ax][ay] == 1 && visit[ax][ay] == 0){ getDFS(ax, ay); } } } } }
반응형
'알고리즘 > Baekjoon' 카테고리의 다른 글
[ Baekjoon ] #1463 1로 만들기 (0) | 2020.03.01 |
---|---|
[ Baekjoon ] #10026 적록색약 (0) | 2020.02.22 |
[ Baekjoon ] #2667 단지 번호 붙이기 (0) | 2020.02.16 |
[ Baekjoon ] #2583 영역 구하기 (2) | 2020.02.13 |
[Baekjoon] #1012 유기농 배추 (0) | 2018.02.19 |