🔗 Problem

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

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;

// 섬의 개수

public class BJ4963 {
	
	static class Point {
		
		int x;
		int y;
		
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	static int w;
	static int h;
	static boolean[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int cnt;
	static Stack<Point> stack = new Stack<>();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			if(w == 0 && h == 0) break;
			
			map = new boolean[h+1][w+1];
			visited = new boolean[h+1][w+1];
			cnt = 0;
			for(int i = 1; i <= w; i++) {
				for(int j = 1; j <= h; j++) {
					map[j][i] = false;
					visited[j][i] = false;
				}
			}
			
			for(int i = 1; i <= h; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= w; j++) {
					int x = Integer.parseInt(st.nextToken());
					if(x == 1) map[i][j] = true;
				}
			}
			
			for(int i = 1; i <= w; i++) {
				for(int j = 1; j <= h; j++) {
					if(!visited[j][i]) {
						if(map[j][i]) dfs(i, j);
						else visited[j][i] = true;
					}
				}
			}
	
			sb.append(cnt).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	private static void dfs(int x, int y) {
		
		stack.add(new Point(x, y));
		visited[y][x] = true;
		
		boolean flag = false;		// 섬이 여러 칸으로 이루어진 경우 판단
		int isOne = 1;				// 섬이 한 칸으로 이루어진 경우 판단
		
		while(!stack.isEmpty()) {
			
			Point poll = stack.pop();
			for(int i = 0; i < dx.length; i++) {
				
				int xx = poll.x + dx[i];
				int yy = poll.y + dy[i];
				if(1 > xx || xx > w || 1 > yy || yy > h) continue;
				
				if(map[yy][xx] && !visited[yy][xx]) {
					stack.add(new Point(xx, yy));
					visited[yy][xx] = true;
					flag = true;
					isOne++;
				}
			}
		}
		
		if(flag || isOne == 1) cnt++;
	}
  
}

📌 Note

아이디어

• DFS로 연결된 섬 찾음
• 입력 시 row, column 바뀌는 게 헷갈렸다.
• boolean flag
  여러 섬이 연결된 경우를 판단하기 위해 boolean으로 잡고 while문 내 if문을 만족할 때 true로 설정했다.
• int isOne
  섬이 한 칸으로 되어 있는 경우를 판단하기 위해 int로 잡고 연결된 칸의 수를 카운트. isOne == 1일 때 한 칸으로 판단.
  isOne이 없다면 flag만으로 한 칸짜리 섬은 카운트하지 못한다.

최근 골드 문제 풀 시간이 없어서 실버만 풀었다😂 특별히 기록할만한 건 없었음