[BOJ/Java] 4963 : 섬의 개수

문제

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

풀이

쉬운 탐색 문제 / dfs 에서 true or false를 리턴하도록 하니까 따로 섬의 개수를 세지 않아도 된다

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int w, h;

	static int[][] map;
	static int[][] dir = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };

	public static boolean dfs(int x, int y) {
		if (x < 0 || y < 0 || x >= h || y >= w)
			return false;

		if (map[x][y] == 1) {

			map[x][y] = 0; // 해당 위치 방문 처리
			for (int d = 0; d < 8; d++) {
				int dx = x + dir[d][0];
				int dy = y + dir[d][1];
				dfs(dx, dy);
			}
			return true;
		}
		return false;
	}

	public static void main(String[] args) throws Exception {
		
		while (true) {
			st = new StringTokenizer(in.readLine(), " ");
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			if(w == 0 && h == 0) return; //종료 조건
			// 섬에 대한 정보를 입력받기
			map = new int[h][w];
			int count = 0;
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < w; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (dfs(i, j))
						count++; // dfs가 수행되는 곳에서 섬의 개수 세어주기
				}
			}
			System.out.println(count);

		}

	}

}

 

느낀점

탐색문제가 익숙해지고 있다 !