백준 골드2 빵집

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

문제

풀이

처음에 문제를 봤을 때 뭔말인지 몰랐다 (항상 몰라...😢)
가스관과 빵집을 파이프로 연결하는데 파이프라인이 첫째 열에서 시작하고 마지막 열에서 끝난다는 말에서 테스트 케이스를 보니 첫번째 열과 마지막 열이 건물(x)가 없는데 뭐지????? 라는 생각이었다.

강사님의 문제 설명을 듣고 이해하게 됐다.

첫번째 열이 빵집의 가스관, 마지막 열이 원웅의 빵집이라 한 것은 진짜 하나의 인덱스가 아니라 그 열 자체였다.

그리고 이 문제에서는 방향 우선순위가 있다.
1. 오른쪽 상단
2. 오른쪽 직선
3. 오른쪽 하단

행을 0부터 아래로 내려가면서 탐색을 한다고 생각하면 위 순서대로 해야 가장 많은 파이프를 연결할 수 있다.
왜냐하면 처음부터 위에서 아래로 대각선을 그어버리면 아무것도 연결하지 못하기 때문.

dfs와 백트래킹을 사용하였다.
(dfs+백트래킹 좀 약한듯 ㅠ)

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

public class Main {
    static String arr[][];
    static boolean visit[][];
    static int R, C, sum = 0;
    static boolean flag;

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        R = Integer.parseInt(stringTokenizer.nextToken());
        C = Integer.parseInt(stringTokenizer.nextToken());

        arr = new String[R][C];
        visit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String str = bufferedReader.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = str.split("")[j];
            }
        }
        for (int i = 0; i < R; i++) {
            flag = false;
            dfs(0, i);
        }
        System.out.println(sum);
    }

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

        if (x == C - 1) {
            flag = true;
            sum++;
            return;
        }

        
        if (check(x + 1, y - 1) && arr[y - 1][x + 1].equals(".")) {
            // 오른쪽 대각선 위 갈 수 있음
            dfs(x + 1, y - 1);
            if (flag) return;
        }
        if (check(x + 1, y) && arr[y][x + 1].equals(".")) {
            // 오른쪽 갈 수 있음
            dfs(x + 1, y);
            if (flag) return;
        }
        if (check(x + 1, y + 1) && arr[y + 1][x + 1].equals(".")) {
            // 오른족 아래 갈 수 있음
            dfs(x + 1, y + 1);
            if (flag) return;
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || y < 0 || x >= C || y >= R || visit[y][x]) {
            return false;
        }
        return true;
    }
}

시간초과

하지만 시간초과가 났다.
도저히 모르겠어서 검색해보았는데 코드가 나랑 다를게 없었다 ...!!
계속 고민했는데 설마 배열을 String으로 해서 더 찾는데 오래걸리나? 싶어 char으로 바꾸고 charAt으로 문자를 뽑아 저장했다.

그랬더니 바로 해결 ㅎ..
배열 타입도 그냥 char로 할 수 있으면 char로 하는게 맘 편할 것 같다

package _240704;

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

public class BOJ_빵집 {
    static char arr[][];
    static boolean visit[][];
    static int R, C, sum = 0;
    static boolean flag;

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        R = Integer.parseInt(stringTokenizer.nextToken());
        C = Integer.parseInt(stringTokenizer.nextToken());

        arr = new char[R][C];
        visit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String str = bufferedReader.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            flag = false;
            dfs(0, i);
        }
        System.out.println(sum);
    }

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

        if (x == C - 1) {
            flag = true;
            sum++;
            return;
        }


        if (check(x + 1, y - 1) && arr[y - 1][x + 1]=='.') {
            // 오른쪽 대각선 위 갈 수 있음
            dfs(x + 1, y - 1);
            if (flag) {
                return;
            }
        }
        if (check(x + 1, y) && arr[y][x + 1]=='.') {
            // 오른쪽 갈 수 있음
            dfs(x + 1, y);
            if (flag) return;
        }
        if (check(x + 1, y + 1) && arr[y + 1][x + 1]=='.') {
            // 오른족 아래 갈 수 있음
            dfs(x + 1, y + 1);
            if (flag) return;
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || y < 0 || x >= C || y >= R || visit[y][x]) {
            return false;
        }
        return true;
    }
}

---

요약

• char 배열 쓸 수 있으면 string 배열 쓰지 말고 char 배열 쓰기 -> 시간초과 날 가능성
• dfs + 백트래킹 연습하기
• 문제 이해 좀 잘 하자 !!!!