[JAVA]백준_4963_섬의 개수

문제링크

www.acmicpc.net/problem/4963

4963번: 섬의 개수

---

DFS

 

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

public class Main {

	static int w,h;
	static int map[][];
	static int dx[] = {0,0,-1,1,-1,-1,1,1};
	static int dy[] = {-1,1,0,0,-1,1,-1,1}; //8방향 탐색
	static boolean isVisited[][];
	static int island = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		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 int[h][w];
			isVisited = new boolean[h][w];
			island = 0 ;// 섬 갯수 초기화
			
			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());
			}//지도 입력
			
			/*for(int i=0;i<w;i++)
				System.out.println(Arrays.toString(map[i])); //지도 확인
*/
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					if(map[i][j] == 1 && !isVisited[i][j]) {
						//System.out.println("현재 섬 시작 위치 ("+i+","+j+")");
						isVisited[i][j] = true;
						dfs(i,j);  //섬이면 dfs로 섬 찾기?
						island++;
					}
				}
			}
			
			System.out.println(island);
			
		}
	}
	
	static void dfs(int row,int col) {
		
		for(int d=0;d<8;d++) {
			int nx = row + dx[d];
			int ny = col + dy[d];
			
			if(nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny] ==0 || isVisited[nx][ny]) continue; //배열 범위 벗어나면 그만두기
			
			//방문하지도 않았고 섬이면
			isVisited[nx][ny] = true;
			//System.out.println("현재 섬은 방문하였습니다. ("+nx+","+ny+")");
			dfs(nx,ny);
			
		}
		return;
	}
	

}

 

---

BFS

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

public class Main {

	static int w,h;
	static int map[][];
	static int dx[] = {0,0,-1,1,-1,-1,1,1};
	static int dy[] = {-1,1,0,0,-1,1,-1,1}; //8방향 탐색
	static boolean isVisited[][];
	static Queue<Node> q = new LinkedList<>();
	static int island = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		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 int[h][w];
			isVisited = new boolean[h][w];
			island = 0 ;// 섬 갯수 초기화
			
			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());
			}//지도 입력
			
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					if(map[i][j] ==1 && !isVisited[i][j]) {
						isVisited[i][j] = true;
						q.offer(new Node(i,j));
						bfs();
					}
				}
			}
			System.out.println(island);
			q.clear();
			
		}
	}
	
	static void bfs() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int d=0;d<8;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny] ==0 || isVisited[nx][ny]) continue; //배열 범위 벗어나면 그만두기
				
				//방문하지도 않았고 섬이면
				isVisited[nx][ny] = true;
				q.offer(new Node(nx,ny)); //큐에 넣어주기
			}
		}
		
		island++;
		
	}
	
	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

}

 

 

---

DFS와 BFS를 사용하여 두 가지 방법으로 풀어보았다.

첫번째가 bfs  두번째가 dfs를 사용하여 푼 결과이다.

차이는 크게 나지않는 것 같다.

 

 

---

DFS 코드 설명

대각선 방향까지 탐색해야하므로 총 8방향을 탐색하면서 dfs를 돌려주었다.

만약 좌표가 배열의 크기를 벗어나거나 이미 방문한 좌표면 continue를 통해서 지나쳐주었다.

방문하지도 않았으며 섬이면 isVisited를 true로 해주고 dfs(nx,ny)를 통해 재귀를 시켜주었다.

 

섬의 크기는 main문에서 dfs문 하나가 끝나면 더해주는 식으로 진행하였다.

섬이고 방문하지 않은 곳이면 현재 섬위치를 시작으로 섬의 갯수를 찾는 것이니 현재 섬의 좌표를 방문표시해주고 dfs()를 통해 섬을 찾았다.

 

 

---

BFS 코드 설명

bfs는 큐를 통해 큐가 빌때까지 돌아야하므로 dfs와 살짝 다르다.

현재 위치를 저장하기 위해 큐에 Queue<int []>를 사용하는 대신 좌표 클래스 Node를 생성하여 Queue<Node>를 통해 진행해 주었다.

bfs는 큐가 빌때까지 진행하면서 찾고, 큐가 끝나면 섬의 개수를  +1 해주었다.

 

메인 문에서는 dfs와 동일하게 진행되었다. 

초기값을 큐에 넣어주기위해 섬이면서 방문하지않았던 곳이면 큐에 삽입해주었다.