[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 문제는 비슷하게 느껴지기 시작하는 것 같다!👩

스르스르~~~ 한 차원(?) 더 높은 문제들에 도전해볼 때가 아닌가...❗❓

 

 

▼아래 더보기를 누르면 코드 전체를 볼 수 있습니다.

[코드 보기]