침투(DFS) - level2

- 침투 문제(백준)

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

 

- 풀이

걸린 시간 : 15~20분

import java.io.*;
import java.util.*;
public class Main {

    public static int M, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // 1. Graph 생성
        int[][] graph = new int[M][N];
        boolean[][] visited = new boolean[M][N];
        for(int i = 0; i < M; i++){
            String str = br.readLine();
            for(int j = 0; j < N; j++){
                graph[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        for(int i = 0; i < N; i++){
            recursion(graph, visited, 0, i);
        }

        int count = 0;
        for(int i = 0; i < N; i++){
            if(visited[M - 1][i]){
                count++;
            }
        }
        if(count == 0){
            bw.write("NO");
        } else {
            bw.write("YES");
        }

        br.close();
        bw.close();
    }

    public static void recursion(int[][] graph, boolean[][] visited, int y, int x){
        if(x < 0 || y < 0 || y == M || x == N){
            return;
        }
        if(graph[y][x] == 1){
            return;
        }
        if(visited[y][x]){
            return;
        }
        
        visited[y][x] = true;
        recursion(graph, visited, y - 1, x);
        recursion(graph, visited, y + 1, x);
        recursion(graph, visited, y, x - 1);
        recursion(graph, visited, y, x + 1);
    }
}

DFS는 코드 길이는 길어보이지만, 정말 간단하다.

핵심은 visited와 y,x의 범위를 잘만 지정해주면 된다.

정답률이 44% 문제인데 접근법만 알면

정말 빠르게 풀 수 있다고 생각한다.

 

백준으로는 처음 풀어보았는데,

프로그래머스와 다르게 정말 귀찮은 작업들을 해줘야 한다.

BufferedReader, BufferedWriter, StringTokenizer 사용해주고

문제의 답은 bw.writer를 이용해서 내보내줘야 한다.

또한, 테스트는 콘솔에 입력예제를 복붙해서 검사해야 한다.

 

정말 너무나 불친절하다.

프로그래머스가 그립다.