[코딩테스트] 백준 - 침투

침투 13565번 [17일차]

시간제한	메모리 제한
1초	512MB

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 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를 출력한다.

 

나의코드

package day17;

import java.io.*;

// 침투 - 13565번
public class Solution1 {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static boolean[][] visited;
    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        //입력
        // 첫번째줄
        // M*N = 섬유물질
        // 상하좌우로 이동 dx, dy 배열지정 - (0,1), (0,-1), (1,0), (-1,0)
        // 방문 체크 배열
        // 위쪽 바깥쪽(outer side) - visited[0][i]
        // 아래쪽 안쪽(inner side) - visited[M][i]
        // 0은 전류가 동함 - 이동가능
        // 1은 전류가 통하지 않음 - 이동 불가능

        //기능
        // 조건 : 섬유물질 밖으로 이동할수 없음 : 범위 지정해주기
        // 4방향으로 둘러보기
        // dfs를 이용 - 재귀

        //출력
        // 아래쪽 안쪽(inner side) - visited[M][i]
        // 안쪽에 visited -true가 있으면 YES
        // 없으면 NO

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        int [][] arr = new int[M][N];
        visited = new boolean[M][N];

        //배열에 담기
        for(int i = 0;i<arr.length;i++){
            String line = br.readLine();
            for(int j = 0;j<arr[0].length;j++) {
                int map = Integer.parseInt(line.substring(j,j+1));
                arr[i][j] = map;
            }
        }
        for(int j = 0;j< arr[0].length;j++){
            if (!visited[0][j] && arr[0][j] == 0) {
                //기능
                dfs(0, j, arr);
            }

        }

        boolean right = false;

        for(int j = 0;j< arr[0].length;j++){
            if(visited[M-1][j]){
                right = true;
                break;
            }
        }

        //출력
        System.out.println(right ? "YES" : "NO");
    }

    // dfs를 이용
    static void dfs(int x, int y, int [][] arr){
        visited[x][y] = true;
        //방문확인

        // 상하좌우 탐색
        for(int i =0; i < 4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            boolean withinBounds = nx >= 0 && ny >= 0 && nx < M && ny < N;
            if(withinBounds && !visited[nx][ny] && arr[nx][ny] == 0){
                dfs(nx,ny,arr);
            }
        }
    }
}

 

 

내 풀이 과정에서는 전체를 다 탐색해봐야했지만

check = false; // 기본 false로 설정

for (int i = 0; i < m; i++) { // 바깥쪽(첫행)에서 안쪽(마지막행)까지 연결되어야 함
    if (map[0][i] == 0 && !visited[0][i]) { // 방문하지 않고 첫행에서 전류가 통하는 곳이라면
        dfs(0, i); // 탐색
    }
}
...
static void dfs(int x, int y) {
    visited[x][y] = true; // 현재위치 방문상태로 변경

    if (x == n-1){
        check = true; // 마지막 행이라면 check = true
        return;
    }

    for (int i = 0; i < 4; i++) { // 네 방향에 대해 탐색
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m  // 범위 벗어나거나 & 전류 통하지 않는 곳  & 방문한 곳이면 넘어감
                || map[nx][ny] == 1 || visited[nx][ny]) continue;

        dfs(nx, ny); // 만족하면 탐색
        if (check) return; // 마지막 행에 도달했다면 메서드 종료(불필요한 연산 줄이는 역할)
    }
}

이런식으로 배열을 체크 해주면 마지막까지 탐색하지 않고 조금더 빠르게 탐색을 끝낼수 있었다