백준 13565 - 침투 (자바 - 그래프)

https://www.acmicpc.net/problem/13565

13565번: 침투

 

* 문제 요약

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투 할 수 있는 섬유물질을 개발하고 있다.

이 섬유물질은 2차원 M x N 격자료 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각하기로 한다.

또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안 쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

 

예를 들어 Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b) 에서는 그렇지 못한다.

 

* 입력

첫째 줄에는 격자의 크기를 나타내는 M(2 <= M <= 1,000) 과 N (2 <= N <= 1,000) 이 주어진다.

M줄에 걸쳐서, N개의 0 또는 1 이 공백없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

 

* 출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES 를 출력한다.

그렇지 않으면 NO 를 출력한다.

 

* 예시

 

* 해결 과정

첫번째 해결법 - 스스로 해결한 방법

입력을 2차원 배열로 받은 다음 2차원 배열의 첫번째 행을 탐색하면서 0 이 발견될 경우 해당 인덱스를 기준으로 위, 아래, 왼쪽, 오른쪽 각각의 방향을 대상으로 dfs 탐색을 수행해서 마지막 행에 도착할 수 있는지 확인하고, 도착할 수 있으면 YES, 그렇지 않으면 NO 를 출력해주었다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int[][] figure;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static boolean check = false;
    static int m, n;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);
        figure = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                figure[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        for (int i = 0; i < n; i++) {
            if (figure[0][i] == 0) {
                dfs(0, i);
            }

            if (check) {
                break;
            } else {
                visited = new boolean[m][n];
            }
        }

        if (check) {
            bw.write("YES\n");
        } else {
            bw.write("NO\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int i, int j) {

        visited[i][j] = true;
        if (i == m - 1) {
            check = true;
        } else {
            for (int x = 0; x < 4; x++) {
                int ii = i + dx[x];
                int jj = j + dy[x];

                if (ii < 0 || jj < 0 || ii >= m || jj >= n) {
                    continue;
                } else if (!visited[ii][jj] && figure[ii][jj] == 0) {
                    dfs(ii, jj);
                }
            }
        }
    }
}

 

두번째 해결법 - 다른 사람 풀이 참고

기본적인 로직은 내 방식과 같았으나, 첫번째 행에서 0 인 동시에 방문하지 않은 인덱스인 경우만 dfs 탐색을 수행하는 것을 확인할 수 있었고, 이 경우가 내 풀이방식보다 처리 시간이 대략 6배 빨랐고, 메모리도 6배 가량 덜 사용한 것을 확인할 수 있었다.

마지막 지점에 도달했는지 아닌지 여부는 visited 배열의 마지막 행을 탐색하면서 true 가 발견되면 YES, 그렇지 않으면 NO 를 출력하는 것으로 해결하였다.

특정 출발점에서 마지막 행에 도착하는 것을 실패한 경우 visited 배열을 초기화 시키고 다음 탐색으로 넘어가는 식으로 풀었었는데, 이와는 달리 이미 앞전의 탐색을 통해 방문한 곳을 dfs 탐색 시작점에서 제외시키는게 주요한 전략 이었던 것 같다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int[][] figure;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int m, n;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);
        figure = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                figure[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        for (int i = 0; i < n; i++) {
            if (figure[0][i] == 0 && !visited[0][i]) {
                dfs(0, i);
            }
        }

        boolean check = false;
        for (int i = 0; i < n; i++) {
            if (visited[m - 1][i]) {
                check = true;
                break;
            }
        }

        if (check) {
            bw.write("YES\n");
        } else {
            bw.write("NO\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int i, int j) {

        visited[i][j] = true;

        for (int x = 0; x < 4; x++) {
            int ii = i + dx[x];
            int jj = j + dy[x];

            if (ii < 0 || jj < 0 || ii >= m || jj >= n) {
                continue;
            } else if (!visited[ii][jj] && figure[ii][jj] == 0) {
                dfs(ii, jj);
            }
        }
    }
}

 

2차원 배열에서 막혀있는 곳을 피해 첫번째 행에서 마지막 행까지 갈 수 있는 경로가 있는지 DFS 탐색을 통해 검증하면 되는 문제이므로 그래프 탐색 문제에 해당된다.