[백준] 3109: 빵집 - JAVA

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;
    }

}