[백준/java] 4963번 : 섬의 개수 - BFS

 

4963번 : 섬의 개수

 

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

4963번: 섬의 개수

 

728x90

 

드디어.. 처음으로 BFS 개념을 어느 곳에서도 참고하지 않고 혼자 힘으로 푼 문제이다

 

문제 자체는 어려운 문제는 아니었다.

 

반응형

 

※ 문제 풀이 접근 방법

(1) 이차원 배열 map으로 배열의 크기 다음으로 입력되는 값들을 입력받는다

(2) map 이차원 배열의 크기와 똑같은 사이즈의 boolean형 이차원 배열을 만들어준다.

(3) 이중으로 for문을 돌면서, map[i][j]가 1이 아니거나 visit[i][j] 이미 방문한 곳이면 건너뛴다

(4) 방문하지 않고 1인 곳이면 큐에 넣어서 넓이 우선 탐색을 진행한다

(5) 이때 방향은 총 8가지의 방향을 탐색해야한다.

 

섬의 개수 문제풀이

(6) 8방향을 탐색해서 주욱 하나로 이어진 것이 하나의 섬이기 때문에, q가 비어있지 않을 때 반복하는 반복문을 나와서 cnt를 증가시킨다.

 

package bfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class LandCnt {
	static int[][] map;
	static boolean[][] visit;
	static int w, h, cnt;
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
	static class Node {
		int y,x;
		
		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		while(true) {
			StringTokenizer st =  new StringTokenizer(br.readLine(), " ");
			w = stoi(st.nextToken());
			h = stoi(st.nextToken());
			cnt = 0;
			
			if(w == 0 && h == 0) break;
			
			map = new int[h][w];
			visit = new boolean[h][w];
			
			for (int i = 0; i < h; i++) {
				String[] strArr = br.readLine().split(" ");
				for (int j = 0; j < w; j++) {
					map[i][j] = stoi(strArr[j]);
				}
			}
			
			bfs();
			
			bw.write(cnt + "\n");
		}
		
		bw.flush();
	}
	
	public static void bfs() {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if(map[i][j] != 1 || visit[i][j]) continue;
				
				Queue<Node> q = new LinkedList<Node>();
				visit[i][j] = true;
				q.add(new Node(i, j));
				
				while(!q.isEmpty()) {
					Node cur = q.poll();
					
					for (int dir = 0; dir < 8; dir++) {
						int ny = dy[dir] + cur.y;
						int nx = dx[dir] + cur.x;
						
						if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
						if(map[ny][nx] == 0 || visit[ny][nx]) continue;
						
						visit[ny][nx] = true;
						q.add(new Node(ny, nx));
					}
				}
				
				cnt++;
			}
		}
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}