[문제풀이] 08-13. 섬나라 아일랜드(DFS)

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0813. 섬나라 아일랜드(DFS)

🗒️ 문제

🎈 나의 풀이

	private static int size;
    private static int[][] world;
    private static int[] dx = {1, 0, -1, 0, 1, -1, 1, -1};
    private static int[] dy = {0, 1, 0, -1, -1, -1, 1, 1};
    private static void DFS(int x, int y) {
        world[x][y] = 0;

        for(int i=0; i<dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<size && ny>=0 && ny<size && world[nx][ny]==1)
                DFS(nx, ny);
        }
    }
    private static int solution() {
        int answer = 0;

        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                if(world[i][j] == 1) {
                    DFS(i, j);
                    answer++;
                }
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        world = new int[size][size];

        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) world[i][j] = sc.nextInt();
        }

        System.out.println(solution());

    }

🖍️ 강의 풀이

  	static int answer=0, n;
	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, int[][] board){
		for(int i=0; i<8; i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1){
				board[nx][ny]=0;
				DFS(nx, ny, board);
			}
		}	
	}
	public void solution(int[][] board){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(board[i][j]==1){
					answer++;
					board[i][j]=0;
					DFS(i, j, board);
				}
			}
		}	
	}

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

💬 짚어가기

해당 문제를 DFS를 이용하여 풀이해보았다. 나의 풀이에서는 지도 전체의 정보를 2차원 배열
world에 보관하였다. 지도를 순회하면서 섬(1)이 발견되었을 때 DFS를 수행하여 섬 전체
땅을 찾도록 하였다.

dx와 dy 배열을 두어 좌표에서 상하좌우 그리고 대각 방향의 움직을 보관하였고, DFS에서
발견되는 섬의 위치에는 0을 담아 중복 탐색을 방지하였다.

DFS에서는 인접한 좌표를 탐색하며 지도 영역 내에서 해당 좌표가 섬인지 판별하였고, 섬인 경우
재귀 호출하여 섬 하나의 전체 영역을 탐색하도록 하였다.

모든 지도 순회를 마쳤을 때 섬의 개수를 반환하여 문제를 해결하였다.
강의에서도 동일한 로직으로 풀이하였다.