[알고리즘 / 백준] 4963 - 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

문제는 위와 같으며, 지도의 정보를 이차원 배열로 저장하고 각 섬을 방문한 적이 있는지 확인하는 이차원 배열을 만든 후, 기본적인 DFS 를 통해 연결된 땅을 모두 방문처리하고 나서 섬의 개수를 증가시키는 방식으로 섬이 몇개인지 확인할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

import sys
sys.setrecursionlimit(10000)  # 재귀함수 범위 제한 수정

# 상하좌우, 대각선까지 이동할 수 있는 방향 저장
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


def dfs(x, y):
    visited[x][y] = True  # 해당 위치의 땅을 방문한 것으로 표시하고

    for d in range(8):  # 상하좌우, 대각선 위치의 땅의 위치를 확인하여
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < h and 0 <= ny < w:  # 해당 위치가 지도내에 존재하고
            if island[nx][ny] == 1 and not visited[nx][ny]:  # 땅이면서 아직 방문하지 않은 경우
                dfs(nx, ny)  # 연결된 땅을 모두 방문하는 함수를 재귀적으로 수행


while True:
    w, h = map(int, sys.stdin.readline().split())  # 지도의 넓이와 높이 입력 받기

	# 둘다 0인 경우 종료
    if w == 0 and h == 0:
        break

	# 지도 내 땅과 바다 위치 이차원 배열로 저장
    island = []
    for _ in range(h):
        island.append(list(map(int, sys.stdin.readline().split())))

	# 지도 내 각 위치를 방문했는지 표시할 이차원 배열 생성
    visited = [[False] * w for _ in range(h)]
    count = 0  # 섬의 개수 표시

	# 지도 내 모든 위치를 확인하면서
    for i in range(h):
        for j in range(w):
            if island[i][j] == 1 and not visited[i][j]:  # 땅이면서 방문하지 않은 경우
                dfs(i, j)  # 해당 위치의 땅과 연결된 땅을 모두 방문 (하나의 섬 확인)
                count += 1  # 섬의 개수 증가

    print(count)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    private static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    private static int w;
    private static int h;

    private static int[][] island;
    private static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        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());

			// w, h 모두 0인 경우 종료
            if (w == 0 && h == 0) {
                break;
            }

			// 지도 내 땅과 바다 위치를 이차원 배열로 저장
            island = new int[h][w];
            for (int i = 0; i < h; i++) {
                island[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }

			// 지도 내 각 위치를 방문했는지 표시할 이차원 배열 생성
            visited = new boolean[h][w];
            int count = 0;  // 섬의 개수를 나타내는 변수

			// 지도 내 모든 위치를 확인하며
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (island[i][j] == 1 && !visited[i][j]) {  // 해당 위치가 땅이면서 아직 방문하지 않은 경우
                        dfs(i, j);  // 해당 위치와 연결된 모든 땅을 방문 (하나의 섬 확인)
                        count += 1;  // 섬의 개수 증가
                    }
                }
            }

            System.out.println(count);
        }
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;  // 해당 위치를 방문 처리하고

		// 상하좌우, 대각선으로 이동할 수 있는 위치를 구하고
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < h && ny >= 0 && ny < w) {  // 다음 위치가 지도 내에 존재하고
                if (island[nx][ny] == 1 && !visited[nx][ny]) {  // 다음 위치가 땅이면서 아직 방문하지 않은 경우
                    dfs(nx, ny);  // 다음 위치와 연결된 땅을 찾아 모두 방문하는 함수를 재귀적으로 수행
                }
            }
        }
    }
}