https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는
www.acmicpc.net
주변 탐색을 통해서, 독립된 섬의 개수를 세는 문제로..
DFS를 통해서 주변을 탐색하고, 연결된 탐색된 연결점을 false로 변환 함.
이렇게 반복하면서, 전체 map중 true인 점을 세면 됨.
public class BOJ4963 {
static int W, H;
static boolean[][] map;
static final int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1};
static final int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
static void dfs(int row, int cul) {
map[row][cul] = false;
for (int i = 0; i < 8 ; i++) {
int nr = row + dx[i];
int nc = cul + dy[i];
if((nr>0) && (nr<=H) && (nc>0) && (nc<=W) && map[nr][nc]) dfs(nr, nc);
}
}
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("res/input_boj4963.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine().trim(), " ");
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new boolean[H+1][W+1];
if((W+H) == 0) break;
for (int i = 1; i <= H ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
for (int j = 1; j <= W ; j++) {
String tmp = st.nextToken();
map[i][j] = (tmp.equals("1"));
}
}
long result = 0;
for (int i = 1; i <= H ; i++) {
for (int j = 1; j <= W ; j++) {
if(map[i][j]) {
result++;
dfs(i,j);
}
}
}
System.out.println(result);
}
}
}