백준- 4963 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

---

DFS, BFS 모두 사용하여 풀 수 있음

방문한 섬 체크를 해주고 방문하지 않은 섬을 만날 때마다 cnt를 1씩 증가시켜주었다.

방문체크방식은 dfs, bfs 동일

---

풀이 1. DFS

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class 섬의개수_DFS {

	static int w,h,cnt;
	static int map[][];
	static boolean v[][];
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("input/섬의_개수.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while(true) {//무한반복
			StringTokenizer st= new StringTokenizer(br.readLine()," ");
			w =Integer.parseInt(st.nextToken());
			h =Integer.parseInt(st.nextToken());
			if(w==0 && h==0) break;//0 0 입력시 종료
            //초기화
			cnt=0;
			map = new int[h][w];
			v = new boolean[h][w];
			
			for (int i = 0; i < h; i++) {
				st= new StringTokenizer(br.readLine()," ");
				for (int j = 0; j < w; j++) {
					map[i][j]= Integer.parseInt(st.nextToken());	
				}
			}//end for
//			print();
			//포문돌다가 1,1인지점있으면 거기부터시작
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(map[i][j]!=0 && !v[i][j]) {//만약 1이고 방문되어지지않았다면
						cnt++;//카운트 +1
                        dfs(i,j);//dfs로 주변 섬 탐색 시작
					}
				}	
			}//end for
			System.out.println(cnt);//섬의 개수 출력
			cnt=0;//무한반복을 위해 초기화
			
		}
		
	}
	private static void dfs(int r, int c) {
		v[r][c]=true;//방문체크
		for (int d = 0; d <8; d++) {//8방탐색
			int nr = r+dr[d];
			int nc = c+dc[d];
			if(nr >=0 && nr <h && nc >=0 && nc< w && !v[nr][nc] && map[nr][nc]==1) {
				//범위안이고 근처에1있고 방문하지않았으면 dfs실행.
				dfs(nr,nc);
			}
			//없으면
		}
		
	}
	static int []dr = {-1,1,0,0,-1,1,1,-1};//상하좌우 우상우하 좌상좌하
	static int []dc = {0,0,-1,1,1,1,-1,-1};//상하좌우 우상우하 좌상좌하


}

---

풀이2. BFS

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class 섬의개수_BFS {

	static int w,h,cnt;
	static int map[][];
	static boolean v[][];
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("input/섬의_개수.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true) {
			StringTokenizer st= new StringTokenizer(br.readLine()," ");
			w =Integer.parseInt(st.nextToken());//열 크기
			h =Integer.parseInt(st.nextToken());//행 크기
			if(w==0 && h==0) break;// 0 0 입력시 종료되도록
			cnt=0;//섬의개수count
			map = new int[h][w];//맵 
			v = new boolean[h][w];//방문배열
			
			for (int i = 0; i < h; i++) {
				st= new StringTokenizer(br.readLine()," ");
				for (int j = 0; j < w; j++) {
					map[i][j]= Integer.parseInt(st.nextToken());	
				}
			}//end for
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(map[i][j]!=0 && !v[i][j]) {// 1이고 방문된 섬이지 않을 경우에 bfs시작
						cnt++;//카운트+1
						bfs(i,j);
					}
				}	
			}//end for
			System.out.println(cnt);
			cnt=0;//카운트 초기화
			
		}
		
	}
	private static void bfs(int r, int c) {
		Queue <Point> Q = new LinkedList<Point>();
		Q.offer(new Point(r,c));//그 좌표를 갖고있는 Point객체를 Queue에 삽입
		v[r][c]=true;//방문체크
		while(!Q.isEmpty()) {//큐가 비지 않을때까지
			Point temp = Q.poll();//poll
			r = temp.r;//r, c값 저장
			c = temp.c;
			
			for (int d = 0; d < 8; d++) {//8방탐색
				int nr = r+dr[d];
				int nc = c+dc[d];
				if(nr>=0 && nr<h && nc>=0 && nc<w) {//범위체크
					if(map[nr][nc]==1&& !v[nr][nc]) {//새로운 좌표의 값이 1이고 그곳이 방문되지않았을경우
						v[nr][nc]=true;//방문체크를 하고
						Q.offer(new Point(nr,nc));//새 좌표를 Queue에 삽입.
					}
				}

			}//end for d
		}
	}
	static int []dr = {-1,1,0,0,-1,1,1,-1};//상하좌우 우상우하 좌상좌하
	static int []dc = {0,0,-1,1,1,1,-1,-1};//상하좌우 우상우하 좌상좌하

	public static class Point{//r,c값을 저장할 클래스
		int r,c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}
		
	}

}