백준 4963 섬의개수 / JAVA

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

4963번: 섬의 개수

 

> 풀이(DFS)

/*
 * 백준 4963 섬의개수
 * #실버2
 * #DFS
 * 23.05.17
 */
public class boj_4963_DFS {

	static int[] dx = {-1,-1,-1,0,1,1,1,0}; 
	static int[] dy = {-1,0,1,1,1,0,-1,-1};
	static int[][] arr;
	static boolean[][] checked;
	static int answer;
	static int w,h;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = "";
		while(true) {
			input = br.readLine();
			if("0 0".equals(input)) break;
			StringTokenizer st = new StringTokenizer(input);
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			arr = new int[h+1][w+1];
			checked = new boolean[h+1][w+1];
			for(int i = 1; i <= h; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int answer = 0;
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(!checked[i][j] && arr[i][j] == 1) {
						answer++;
						DFS(i,j);
					}
				}
			}
			System.out.println(answer);
		}
	}
	
	public static void DFS(int x, int y) {
		checked[x][y] = true;
		for(int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx > 0 && nx <= h && ny > 0 && ny <= w) {
				if(!checked[nx][ny] && arr[nx][ny] == 1) {
					DFS(nx,ny);
				}
			}
		}
	}
}

 

> 풀이(BFS)

/*
 * 백준 4963 섬의개수
 * #실버2
 * #BFS
 * 23.05.18
 */
public class boj_4963_BFS {

	static int[] dx = {-1,-1,-1,0,1,1,1,0}; 
	static int[] dy = {-1,0,1,1,1,0,-1,-1};
	static int[][] arr;
	static boolean[][] checked;
	static int answer;
	static int w,h;
	static class Node {
		int x, y;
		
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = "";
		while(true) {
			input = br.readLine();
			if("0 0".equals(input)) break;
			StringTokenizer st = new StringTokenizer(input);
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			arr = new int[h+1][w+1];
			checked = new boolean[h+1][w+1];
			for(int i = 1; i <= h; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int answer = 0;
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(!checked[i][j] && arr[i][j] == 1) {
						answer++;
						BFS(i,j);
					}
				}
			}
			System.out.println(answer);
		}
	}
	
	public static void BFS(int x, int y) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(x,y));
		checked[x][y] = true;
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			for(int i = 0; i < 8; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx > 0 && nx <= h && ny > 0 && ny <= w) {
					if(arr[nx][ny] == 1 && !checked[nx][ny]) {
						checked[nx][ny] = true;
						queue.offer(new Node(nx,ny));
					}
				}
			}
		}
	}

}