[BOJ] 백준 13565 - 침투 풀이

1. 문제

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

13565번: 침투

 

2. 풀이

DFS로 문제를 해결하였다. 주어진 1과 0을 2차원 배열에 넣었다고 가정한다면 문제에서 말하는 가장 바깥쪽은 배열의 첫번째 행, 가장 안쪽은 배열의 마지막 행이된다. DFS를 돌릴 때 Main 함수에서 배열의 첫 번째 행을 반복으로 돌리면서 DFS를 탐색해주고 DFS 함수 안에서 탐색을 진행하던 도중 인자로 받은 x 값이 마지막 행에 도착했다면 전류가 가장 안쪽까지 도달한 것이므로 flag 변수를 참으로 바꾼다.

 

3. 소스 코드

import java.io.*;
import java.util.*;

class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int M;
    static int N;
    static boolean flag = false;
    public static void main(String[] args) throws Exception {
        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());

        map = new int[M][N];
        visited = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(Character.toString(input.charAt(j)));
            }
        }

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

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

    private static void dfs(int x, int y) {
        visited[x][y] = true;

        if (x == M - 1) {
            flag = true;
        }

        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (xf >= 0 && yf >= 0 && xf <= M - 1 && yf <= N - 1 && !visited[xf][yf] && map[xf][yf] == 0) {
                dfs(xf, yf);
            }
        }
    }
}