[백준]13565번 침투 - Java

문제

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

13565번: 침투

 

 

풀이

간단한 DFS, BFS 문제인 듯하다

그래서 DFS로, BFS로 각각 사용해서 풀어봤음

 

일단 DFS는 그냥 맨 윗줄에서 0이면 DFS 들어가고 돌면서 0인 칸을 2로 바꿔줌

위에서 0인 애들 다 돌렸으면 맨 밑줄에서 2인 애가 나오면 그건 전기가 통하는 거고 안나오면 안통하는거

그니까 2가 나오면 YES 출력하고 System.exit(0);으로 시스템 종료.

안나오면 NO 출력!

 

사실 BFS도 똑같음 맨 윗줄에서 0이면 BFS 들어가고 돌면서 뭐시기 뭐시기 ~~

아래는 DFS, 위는 BFS로 푼거!

 

보면 BFS로 푼게 시간이 반토막이라 개꿀이네 왜지

암튼 두번 풀어봤습니다~

 

 

코드

DFS 풀이

// 13565번 침투
// https://www.acmicpc.net/problem/13565

package BAEKJOON;

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

public class Num13565_침투 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

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

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

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < M; i++) {
            if (map[0][i] == 0) {
                solution(0, i);
            }
        }

        for (int i = 0; i < M; i++) {
            if (map[N - 1][i] == 2) {
                System.out.println("YES");
                System.exit(0);
            }
        }
        System.out.println("NO");
    }

    private static void solution(int r, int c) {
        if (visited[r][c] || map[r][c] != 0) {
            return;
        }

        visited[r][c] = true;
        map[r][c] = 2;

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                continue;
            }

            if (!visited[nr][nc] && map[nr][nc] == 0) {
                solution(nr, nc);
            }
        }
    }
}

 

BFS 풀이

// 13565번 침투
// https://www.acmicpc.net/problem/13565

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Num13565_침투2 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    public static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

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

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

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < M; i++) {
            if (map[0][i] == 0) {
                solution(0, i);
            }
        }

        for (int i = 0; i < M; i++) {
            if (map[N - 1][i] == 2) {
                System.out.println("YES");
                System.exit(0);
            }
        }
        System.out.println("NO");
    }

    private static void solution(int y, int x) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(y, x));

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            int r = temp.r;
            int c = temp.c;

            if (map[r][c] != 0) {
                continue;
            }

            visited[r][c] = true;
            map[r][c] = 2;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                    continue;
                }

                if (!visited[nr][nc] && map[nr][nc] == 0) {
                    queue.offer(new Node(nr, nc));
                }
            }
        }
    }
}