[Ch.08 - DFS / BFS] 13. 섬나라 아일랜드 #

13. 섬나라 아일랜드

 

설명

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.

각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

만약 위와 같다면 섬의 개수는 5개입니다.

입력

첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.

두 번째 줄부터 격자판 정보가 주어진다.

출력

첫 번째 줄에 섬의 개수를 출력한다.

예시 입력 1 

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

예시 출력 1

5

---

1. board[i][j]==1이면, answer++;
   1. i, j를 시작점으로 DFS 호출
   2. 뻗은 후에는 0으로 초기화
2. 모두 뻗은 후에는 DFS 종료후, board[i][j]=1 체크

 

---

import java.util.Scanner;

public class Main {

	static int n,answer = 0;
	static int[][] board, dis;
	static int[][] check = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		board = new int[n][n];
		dis = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				board[i][j] = in.nextInt();
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 1) {
					answer++;
					DFS(i, j);
				}
			}
		}
		System.out.println(answer);
	}

	static void DFS(int x, int y) {
		board[x][y]=0;
		dis[x][y]=answer;
		for (int i = 0; i < 8; i++) {
			int nx = x + check[i][0];
			int ny = y + check[i][1];
			if (nx>=0&&ny>=0&&nx<n&&ny<n&&board[nx][ny] == 1) {
				DFS(nx, ny);
			}
		}
	}
}

 

+) 세련된 풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
	static int[][] board, dis;
	static int n;
	static int m = 0;
	static int answer = 0;

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

	public void DFS(int x, int y) {
		for (int i = 0; i < 8; i++) {
			board[x][y] = 0;
			dis[x][y] = answer;
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny] == 1) {
				DFS(nx, ny);
				
			}

		}

	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		board = new int[n][n];
		dis = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				board[i][j] = kb.nextInt();
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
		if (board[i][j] == 1) {
			answer++;
			T.DFS(i, j);
		}
	}
}
		System.out.println(answer);

	}
}

 

 

(1) 섬나라 확인 할 때마다, answer++; 하고, 같은 섬 찾는 DFS 수행

(2) DFS를 수행하면서, for문으로 다시 같은 섬 찾는 DFS 수행한다. -> 재귀함수 이용

(3) 따라서 같은 섬일 경우 answer++가 늘어나지 않는 원리 이용

 

import java.util.*;
class Pos{
  public int x,y;
  Pos(int x, int y){
    this.x=x;
    this.y=y;
  }
  public boolean isValid(int width, int height){
    if(x<0||x>=width||y<0||y>=height){
      return false;
    }
    return true;
  }
}
public class Main {
  static int n;
  static int answer=0;
  static int[][]arr,chk;
  static final int[][]dis= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    arr = new int[n][n];
    chk = new int[n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(arr[i][j]==1){
          answer++;
                  DFS(new Pos(i,j));

        }
      }
    }
    
    System.out.println(answer);                 
  }
  static void DFS(Pos p){
    for(int i=0;i<8;i++){
      arr[p.x][p.y]=0;
      chk[p.x][p.y]=answer;
      Pos ps=new Pos(p.x+dis[i][0], p.y+dis[i][1]);
      if(ps.isValid(n,n) && arr[ps.x][ps.y]==1)
        DFS(ps);
    }
  }
}

 

사실상 체크 배열이 필요가 없다.

import java.util.*;
class Pos{
  public int x,y;
  Pos(int x, int y){
    this.x=x;
    this.y=y;
  }
  public boolean isValid(int width, int height){
    if(x<0||x>=width||y<0||y>=height){
      return false;
    }
    return true;
  }
}
public class Main {
  static int n;
  static int answer=0;
  static int[][]arr;
  //,chk;
  static final int[][]dis= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    arr = new int[n][n];
    //chk = new int[n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(arr[i][j]==1){
          answer++;
                  DFS(new Pos(i,j));

        }
      }
    }
    
    System.out.println(answer);                 
  }
  static void DFS(Pos p){
    for(int i=0;i<8;i++){
      arr[p.x][p.y]=0;
      //chk[p.x][p.y]=answer;
      Pos ps=new Pos(p.x+dis[i][0], p.y+dis[i][1]);
      if(ps.isValid(n,n) && arr[ps.x][ps.y]==1)
        DFS(ps);
    }
  }
}