[백준] 3109: 빵집 - JAVA

in Algorithm on 그래프 이론

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

풀이

첫번째 열에서 마지막 열까지 파이프를 이어야한다. 이때 이동은 { -1, 1 }, { 0, 1 }, { 1, 1 } 으로 할 수 있다.

탐색 방향 순서를 위에서부터 채우기 위해 -1, 0, 1 순으로 탐색한다.

배열에 방문했다는 체크를 하면서 탐색하며, 마지막까지 같다면 개수를 늘리고, true를 리턴한다. 실패할 경우 false를 리턴하여 종료한다.

방문 체크를 먼저 하고 탐색을 보냈기 때문에 실패한 칸은 다시 가보지 않아도 되게하여 시간초과를 해결할 수 있었다.

메모리: 34748KB

시간: 400ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int r;
        int c;

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

    static int[][] vector = { { -1, 1 }, { 0, 1 }, { 1, 1 } };

    static int n, m, answer;
    static char[][] board;

    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());

        board = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        answer = 0;
        for (int i = 0; i < n; i++) {
            dfs(i, 0);
        }

        System.out.println(answer);
    }

    private static boolean dfs(int r, int c) {
        if (c == m - 1) {
            answer++;
            return true;
        }

        for (int k = 0; k < 3; k++) {
            int nr = r + vector[k][0];
            int nc = c + vector[k][1];

            if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
                continue;
            }

            if (board[nr][nc] == '.') {
                board[nr][nc] = 'o';
                if (dfs(nr, nc)) {
                    return true;
                }
            }
        }

        return false;
    }

}