[백준] 4963 섬의 개수(DFS)

 

접근 방법

• BFS로 풀었던 것처럼, 각 영역마다 방문을 시작하지 않은 곳이 있으면 방문을 시작해준다. 
• 이동 경로를 int[] dx, int[] dy로 선언하여 더해준다. 

 

특이점

• 길찾기 문제를 DFS로 처음 풀어본 문제. 
• 이동 방향이 4가지가 아닌 대각선까지 포함하여 8가지이다.

 

<오답 코드>

while문 안에 while문을 통해서 방문하지 않은 곳들을 찾아주려 했었다. 

하지만 다시 생각해 보면, DFS를 통해서 나오는 시점에는 모두 탐색을 했기 때문에 while문으로 다시 체크해 줄 필요가 없었다. 

그리고 isAllVisited 탈출 코드도 추가해 주다 보니 더 복잡해지게 되었다. 

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOK_4963 {
    static int[][] graph;
    static boolean[][] visited;
    static int x;
    static int y;
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> array = new ArrayList<>();
        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            if(x == 0 && y == 0) break;
            graph = new int[x][y];
            visited = new boolean[x][y];
            int startX = 0;
            int startY = 0;
            boolean isAllVisited;
            int cnt = 1;

            for (int i = 0; i < x; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < y; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 탐색 시작
            while(true) {
                dfs(startX, startY);
                isAllVisited = true;

                // 모두 돌았는지 체크
                for (int i = 0; i < x; i++) {
                    if(x == 1 && y == 1 && graph[0][0] == 0){
                        cnt =0;
                        break;
                    }
                    for (int j = 0; j < y; j++) {
                        if (graph[i][j] == 1 && !visited[i][j]) {
                            cnt++;
                            startX = i;
                            startY = j;
                            isAllVisited = false;
                            break;
                        }
                    }
                    if(!isAllVisited) break;
                }
                if(isAllVisited){
                    array.add(cnt);
                    break;
                }
            }
        }

        for (int i = 0; i < array.size(); i++) {
            System.out.println(array.get(i));
        }
    }
    public static void dfs(int startX, int startY){
        if(graph[startX][startY] == 1)
            visited[startX][startY] = true;

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

        for(int i=0; i<dx.length; i++){
            int nextX = startX + dx[i];
            int nextY = startY + dy[i];

            if(nextX < 0 || nextY < 0 || nextX >= x || nextY >= y)
                continue;
            if(visited[nextX][nextY] || graph[nextX][nextY] != 1)
                continue;

            visited[nextX][nextY] = true;
            dfs(nextX, nextY);
        }
    }
    public static void main(String[] args) throws IOException {
        solution();
    }
}

 

<정답 코드>

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOK_4963 {
    static int[][] graph;
    static boolean[][] visited;
    static int x;
    static int y;
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> array = new ArrayList<>();
        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            if(x == 0 && y == 0) break;
            graph = new int[x][y];
            visited = new boolean[x][y];
            int startX = 0;
            int startY = 0;
            boolean isAllVisited;
            int cnt = 1;

            for (int i = 0; i < x; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < y; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 탐색 시작

            // 모두 돌았는지 체크
            for (int i = 0; i < x; i++) {
                if(x == 1 && y == 1 && graph[0][0] == 0){
                    break;
                }
                for (int j = 0; j < y; j++) {
                    if (graph[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);

                        cnt++;

                    }
                }
            }
            array.add(cnt-1);
        }

        for (int i = 0; i < array.size(); i++) {
            System.out.println(array.get(i));
        }
    }
    public static void dfs(int startX, int startY){
        if(graph[startX][startY] == 1)
            visited[startX][startY] = true;

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

        for(int i=0; i<dx.length; i++){
            int nextX = startX + dx[i];
            int nextY = startY + dy[i];

            if(nextX < 0 || nextY < 0 || nextX >= x || nextY >= y)
                continue;
            if(visited[nextX][nextY] || graph[nextX][nextY] != 1)
                continue;

            visited[nextX][nextY] = true;
            dfs(nextX, nextY);
        }
    }
    public static void main(String[] args) throws IOException {
        solution();
    }
}