[BOJ] 4963. 섬의 개수 (Java)

문제 링크 / level: Silver I

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

4963번: 섬의 개수

 

 

내가 생각한 풀이

이 문제도 다른 사람이 만들어 둔 문제집에 있었던 문제다. 예전에 추천받았던 적 있었는데, 그때는 내가 BFS를 잘 몰라서 시도도 못했었는데 이번 기회에 한 번 풀어봤고, 풀었다. 나 많이 성장했잖아?😎✌

 

이 문제 역시 바로 직전에 풀었던 [1743. 음식물 피하기]처럼 전형적인 BFS 문제이며 flood fill문제다.

1: 땅, 0: 바다인데 바다는 당연히 갈 수 없고 1로 이어진 곳들의 개수를 세면 된다. 대신 4방이 아닌 8방이다. 상하좌우 뿐만 아니라 대각선까지 이동할 수 있다는 것이 특징!

내가 느끼기에는 BFS - flood fill 계의 바이블과 같은 [2667. 단지번호붙이기] 문제와 크게 다르지 않다. 다만 방향이 추가되었다는 점만 다를 뿐.

 

하나 유의할 점은 이 문제는 입력되는 테스트 케이스의 수가 정해져있지 않고 마지막에 0 0 이 입력되면 입력이 끝난다는 것이 특징이라면 특징이다. 횟수가 정해져 있지 않기 때문에 while문을 사용해줘야겠쥬?🤗 그리고 또 하나는 h와 w를 입력받는 순서에 낚이지 말 것!! 높이와 너비를 잘 구분해서 배열의 사이즈를 지정해줘야 한다.

 

코드를 작성해보자!!

// 핵심 코드
cnt = 0;
for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {
		if(map[i][j] == 1 && visited[i][j] == 0) {
			bfs(i,j,++cnt);
		}
	}
}
System.out.println(cnt);

문제에서 원하는 출력은 섬의 개수이기 때문에 나는 cnt 변수를 활용해서 bfs를 한 번 실행할 때마다 cnt 값을 증가시켰고, 모든 bfs를 다 수행한 후 최종적으로 cnt에 들어있는 값을 출력해줬다.

이렇게 하면 visited 배열에서 첫 번째 섬은 전부 1로 보일 것이고, 두 번째 섬은 전부 2, 세 번째 섬은 전부 3.. 이런 형태가 될 것이다.

 

간단한 BFS문제인 만큼 가벼운 맘으로 코드를 작성하고 실행시켰다.

응 아니야~

처음에 틀렸습니다가 떠서 당황스러웠는데 알고 보니 0 0을 입력받았을 때 그대로 프로그램이 종료되어야 하는데, 내 프로그램에서는 0을 출력하고 종료되었다. 즉, while문의 조건을 잘못 짠 것이어서 바로 호다닥(메다닥) 바꿔주고 가볍게 성공!!!🤗🎉 좋아~~  앞으로는 이런 과정도 좀 줄여가보자구~~~

 

그나저나 이제 슬슬 대부분의 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;
	/* @date: 2020/04/19
	* @author: psS2mj
	* @brief: BOJ_4963_섬의 개수 */
	public class Main_4963_섬의개수 {
	static int w = 1, h = 1, cnt;
	static int[][] map, visited;
	static Queue<int[]> que = new LinkedList<int[]>();
	public static void main(String[] args) throws IOException {
	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;}
	map = new int[h][w];
	visited = new int[h][w];
	for (int i = 0; i < h; i++) {
	StringTokenizer st2 = new StringTokenizer(br.readLine());
	for (int j = 0; j < w; j++) {
	map[i][j] = Integer.parseInt(st2.nextToken());
	}
	}
	// 1: 땅, 0: 바다
	cnt = 0;
	for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {
	if(map[i][j] == 1 && visited[i][j] == 0) {
	bfs(i,j,++cnt);
	}
	}
	}
	System.out.println(cnt);
	}
	} // main
	// 위부터 시계 방향으로
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
	private static void bfs(int y, int x, int cnt) {
	que.clear();
	que.add(new int[] {y,x});
	visited[y][x] = cnt;
	while(!que.isEmpty()) {
	int[] curr = que.poll();
	int cy = curr[0];
	int cx = curr[1];
	for (int d = 0; d < 8; d++) {
	int ny = cy + dy[d];
	int nx = cx + dx[d];
	if(!check(ny,nx)) {continue;}
	if(map[ny][nx] == 1 && visited[ny][nx] == 0) {
	visited[ny][nx] = cnt;
	que.add(new int[] {ny,nx});
	}
	}
	}
	}
	private static boolean check(int ny, int nx) {
	if(ny<0 || ny>=h || nx<0 || nx>=w) {return false;}
	return true;
	}
	} // class

view raw Main_4963_섬의개수.java hosted with ❤ by GitHub