[자바] 백준 13565 - 침투 (java)

목차

문제 : boj13565

 

 

필요 알고리즘

• 그래프 탐색 (bfs, dfs)
  
  • 약간의 아이디어만 생각나면 dfs나 bfs 같은 그래프 탐색으로만 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  주어진 격자에서 맨윗줄 중 흰색(0)칸을 찾아 거기서부터 BFS를 계속 진행한다면 좀 귀찮다. 약간의 아이디어를 더한다면 BFS 한방에 해결할 수 있다.

 

  아이디어는 생각보다 간단한데, 주어진 격자(이미지 좌측)의 맨위와 맨 아래에 한줄씩 추가(이미지 우측)하면 된다.

 

  위에 추가한줄은 전부 흰색(0)으로 생각하고, 맨 아래줄은 별도로 목표점이라 지정해둔다. 그리고 새롭게 추가된 맨 윗줄 아무곳에서나 출발하면 된다. 그럼 기존 격자의 맨 윗줄 중 흰칸을 찾는걸 안해도 된다. 이제 새로운 맨 윗줄의 아무곳에서나 출발해서 저 빨간색 지점에 도착하는지만 보면 된다.

 

  BFS 구현을 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고해보자.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int GOAL = 100;

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

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int[][] arr = new int[r+2][c];
        Arrays.fill(arr[r+1], GOAL);
        for (int i = 1; i <= r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j)-'0';
            }
        }

        Queue<Pos> q = new ArrayDeque<>();
        q.add(new Pos(0, 0));
        arr[0][0] = 1;
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            int cr = cur.r;
            int cc = cur.c;
            for (int a = -1; a <= 1; a++) {
                for (int b = -1; b <= 1; b++) {
                    if (((a^b)&1)!=1) continue;
                    int nr = cr+a;
                    int nc = cc+b;
                    if (nr<0||nr>r+1||nc<0||nc>=c||arr[nr][nc]==1) continue;
                    if (arr[nr][nc] == GOAL) {
                        System.out.println("YES");
                        return;
                    }
                    arr[nr][nc] = 1;
                    q.add(new Pos(nr, nc));
                }
            }
        }
        System.out.println("NO");
    }
}

class Pos {
    int r, c;

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