섬의 개수

1 초

128 MB

40870

20479

14687

49.051%

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이

서로의 포함관계를 구할 수 있는 알고리즘에는 DFS와 유니온 파인드가 있습니다.

원소가 많을수록 유니온 파인드가 유리하지만 배열의 크기가 50x50이므로 DFS로 빠르게 구현할 수 있다고 보았습니다.

지도 구현

땅 아니면 바다이므로 값은 2개로 나타낼 수 있습니다.

2차원 불린 배열을 통해 나타냅니다.

입력값

w h 순으로 주어지고 0 0을 입력 받는 순간 전체 종료합니다.

특이한 점은 너비 높이 = 열 / 행 으로 주어진다는 점입니다.

그래서 순서에 주의해서 반복문을 이용해 값을 넣어줍니다.

while(true) { 
    st = new StringTokenizer(br.readLine());
    int w = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());

    if(w==0 && h==0) break;

    boolean[][] map = new boolean[h][w];

    for(int i=0; i<h; i++) { //행은 h
        st = new StringTokenizer(br.readLine());
        for(int j=0; j<w; j++) { // 열은 w 
            if(st.nextToken().equals("1")) {
                map[i][j] = true;
            }
        }
    }
}

DFS

영역 표시를 위해 섬에 포함된 땅 어느 부분을 밟는 순간 1을 세어주고

그와 동시에 연결된 모든 땅을 방문 표시함으로 조사했다라는 표시를 남깁니다.

지도를 재활용하지 않기 때문에 방문체크 배열을 만들지 않고 땅을 아예 false로 바꾸어(지워서) 바다로 만듭니다.

변경사항

검사하다 배열 밖으로 벗어날 수 있으므로 w,h 값을 메소드의 파라미터로 넣어주거나 정적변수로 할당합니다.

static int w,h,cnt; // main메소드 바깥 부분에 정적 변수로 할당하고 

static void dfs(int row, int col) { // 메소드 생성

}

구현

바깥 범위라면 현재 메소드를 종료하도록 하고 대각 방향까지 넣어줍니다.

	static int[] dx = {0,0,1,-1,1,-1,-1,1}; //8방좌표
	static int[] dy = {1,-1,0,0,1,-1,1,-1};
	
	static void dfs(int row, int col) {
		if(row<0 || row>=h || col<0 || col>=w || !map[row][col]) return;
        //경계값 조건 + 만약 밟은 곳이 바다라면 종료
        
		map[row][col] = false; //현재가 땅이라면 바다로 바꿈
		
		for(int i=0; i<8; i++) {
			dfs(row+dx[i],col+dy[i]);
		}
	}

카운트

한 번 땅을 밟는 순간 연결된 모든 구역을 바다로 만들면서 1을 카운트합니다.

전체 지도를 탐색하면서 이를 반복해줍니다.

전체 코드

import java.io.*;
import java.util.*;
public class Main {
	static int w,h,cnt;
	static boolean[][] map;
	
	static int[] dx = {0,0,1,-1,1,-1,-1,1}; //8방좌표
	static int[] dy = {1,-1,0,0,1,-1,1,-1};
	
	static void dfs(int row, int col) {
		if(row<0 || row>=h || col<0 || col>=w || !map[row][col]) return;
		
		map[row][col] = false;
		
		for(int i=0; i<8; i++) {
			dfs(row+dx[i],col+dy[i]);
		}
	}
	

public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	
	while(true) { 
		st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		cnt = 0;
		if(w==0 && h==0) break;
		
		map = new boolean[h][w];
		
		for(int i=0; i<h; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<w; j++) {
				if(st.nextToken().equals("1")) {
					map[i][j] = true;
				}
			}
		}
		
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(map[i][j]) {
					cnt++;
					dfs(i,j);
				}
			}
		}
		System.out.println(cnt);
	}

}
}

저작자표시