JAVA 알고리즘 : 섬의 개수[백준 4963]

스터디사이트 : https://www.acmicpc.net/

JAVA 알고리즘 : 섬의 개수[백준 4963]

※ 문제 Url
    https://www.acmicpc.net/problem/4963

그래프 알고리즘 분야 중 입문과정인듯하다..

여러 구글링을 통해 원리를 알아냈는데 깨우치기까지 시간이 참 오래도걸렸다 ㅡㅡㅋ

※ 해결법 

내가 머릿속으로 정리된 이 문제에서의 해결법은,

1. 테스트케이스마다 섬(1)과 바다(0)의 정보가 입력된 그대로 int[][] 2차원배열을 만든다.

2. 섬과 바다 정보가 들어있는 2차원 int[][] 배열을 탐색해서 섬(1)을 발견하면, 섬의 갯수를 1씩 증가 시킨다.

2-1. 섬을 발견한 위치의 value를 1 -> 0으로 바꾼다.

2-2. 섬을 발견한 위치 근처에 붙어있는 섬이 있는 지 탐색한다.

2-3. 그 위치 근처에 섬이 있다면, 2-1과 2-2를 반복한다. 더이상 근처에 섬이 없을때까지.

그런데,

 2-1 단계를 왜 하냐면, 아래 그림을 보라.

노란색으로 색칠한 곳이 현재 내가 검사하는 대상이다. 섬을 발견한 위치.

그 다음 단계인 <NEXT>를 보면, 

이 단계가 위의 2-1단계라고 보면 되는데, 빨간색 화살표와 파란색 화살표가 있다.

옆에도 섬(1)이고, 아래도 섬(1)이기 때문에, 반복문을 돌다가 가장 먼저 발견한 곳으로 가는 것이다.

<NEXT - RED>나 <NEXT - BLUE>단계를 보면,

만약에 저 그림과 달리 검사대상을 1 -> 0 으로 바꾸지 않고 그대로 1로 냅뒀을 때

우리가 검사했던 대상으로 다시 되돌아가지 말라는 법이 없지 않는가?

그렇게되면 무한루프에 빠질 수 있기 때문에 검사대상을 1 -> 0으로 바꾸는 것이다.

그리고 나는 1번단계에서 int[][] 배열 정의하는 방식을 특이하게 행과 열에다가 2씩 크기를 더 늘려서 만들었다.

이유는 검사대상 주위의 인덱스들을 탐색할때 모서리나 귀퉁이에 있으면 IndexOutOfBoundsException이 뜰까봐..

하지만 그러한 것을 걸러내는 기능을 하는 메소드도 얼마든지 만들 수 있다. 구글링하면 다른 사람들이 코딩한 것 대부분이 그렇다 ㅋ

그러나 나는 이 코드로도 맞았습니다! 를 얻어냈으므로..ㅋ 나중에 차차 연구를 ㅋ

※ 내가 푼 코드

태클 얼마든지 환영합니다.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class Main {
	// 섬과바다 표시배열
	int[][] island;
	// 섬과바다 검사여부배열
	boolean[][] isCheck;
	public static void main(String[] args) throws IOException {
	new Main();
	} //end main()
	Main() throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer token = null;
	StringBuilder sb = new StringBuilder();
	int islands = 0;
	while (true) {
	// TestCase마다 섬 갯수 초기화
	islands = 0;
	String inputLine = br.readLine();
	if (inputLine.equals("00") || inputLine.equals("0 0")) break;
	// line 1.
	token = new StringTokenizer(inputLine, " ");
	int width = Integer.parseInt(token.nextToken());
	int height = Integer.parseInt(token.nextToken());
	// 주어진 입력범위 밖은 모두 바다 (value = 0) 라는 정보를 넣기위해
	// 섬이 붙어있는 지 검사 시에 검사대상 주위를 둘러싼 인덱스를 구하기위해 IndexOutofBounds가 안 나게 하기위해
	island = new int[height+2][width+2];
	// line x(2~height)
	// island[][] 배열값 채워넣기
	for (int n = 1; n < height+1; n++) {
	token = new StringTokenizer(br.readLine(), " ");
	int tokenIndex=1;
	while(token.hasMoreTokens()){
	int element = Integer.parseInt(token.nextToken());
	island[n][tokenIndex] = element;
	tokenIndex++;
	}
	} //end for
	// * 배열을 탐색해 가며 1인 요소는 0을 만들고, 주위에 1인 요소를 발견하면 같은방식으로 1이 끊기는 위치까지 탐색한다.
	for(int h=1; h<height+1; h++){ // 행
	for(int w=1; w<width+1; w++){ // 열
	if(island[h][w]==1){
	islands++;
	getIslands(h, w);
	}
	} //end for
	} //end for
	sb.append(islands+"\n");
	} //end while
	// 결과출력
	System.out.println(sb.toString());
	} // end Main_2()
	public void getIslands(int h, int w){
	// 검사대상. 즉 1이 표시된 위치에 대해서 0으로 바꿈
	island[h][w] = 0;
	// 대상을 둘러싸는 인덱스
	// ex) 대상 [1,1] : 주위 [0,0] [0,1] [0,2] / [1,0] [1,2] / [2,0] [2,1] [2,2]
	int[] search_h = {-1, -1, -1, 0, 0, 1, 1, 1};
	int[] search_w = {-1, 0, 1, -1, 1, -1, 0, 1};
	for(int i=0; i<search_h.length; i++){
	int around_h = h + search_h[i];
	int around_w = w + search_w[i];
	// 주위에 1인 위치를 발견하면 재귀호출하여 그 위치에서도 근처에 1이 있는지 탐색.
	if(island[around_h][around_w]==1){
	getIslands(around_h, around_w);
	}
	} //end for
	} //end getIslands()
	}

view raw Island_4963.java hosted with ❤ by GitHub