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이 뜰까봐..

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

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

※ 내가 푼 코드

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