[백준] 4963 : 섬의 개수(DFS)

알고리즘 기초 2 / 2

DAY - 4

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

4963번: 섬의 개수

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

---

정말 풀고나서는 쉬운문제 였는데 dx, dy를 잘못잡은것과 if문의 조건걸기를 자꾸 실수해서 시간이 오래걸렸던 문제,, 구현이나 문법적으로는 전혀 문제가 없었고 앞으로 문제를 풀 때에는 문제를 잘 읽고 풀이를 시작하자!!

package day1003;

import java.io.IOException;
import java.util.Scanner;

public class Baekjoon_4963_섬의개수_DFS {

	static int w, h;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { 1, -1, 0, 0, -1, -1, 1, 1 };
	static int[] dy = { 0, 0, -1, 1, 1, -1, 1, -1 };

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);

		while (true) {

			w = sc.nextInt();
			h = sc.nextInt();

			if (w == 0 && h == 0)
				break;

			map = new int[h][w];
			visit = new boolean[h][w];

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			int cnt = 0;

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(map[i][j]==1 && !visit[i][j]) {
						dfs(i,j);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
		sc.close();
	}

	private static void dfs(int x, int y) {
		visit[x][y] = true;
		
		for (int k = 0; k < 8; k++) {
			int nx = x+dx[k];
			int ny = y+dy[k];
			
			if(nx >= 0 && ny >= 0 && nx < h && ny < w && map[nx][ny]==1 && !visit[nx][ny])
				dfs(nx,ny);
		}
	}
}