백준 - 빵집(3109)

⭐ 문제링크

오늘 풀어본 문제는 제목 보고 빵 먹고 싶어서 선정해본 문제입니다.

1. 문제풀이

첫 번째 열에는 원웅이가 훔치고자 하는 다른 집의 파이프관입니다.
마지막 열에는 원웅이의 빵집 파이프입니다.

파이프라인 기준
1. 오른쪽 위, 오른쪽, 오른쪽 아래 3가지의 방향으로만 이동 가능
2. 파이프의 라인끼리 겹쳐서는 안됨.
3. 파이프는 건물을 통과할 수 없음.

2. 접근법

해당 문제를 보고 파이프 라인이 최대한 첫 번째 행 또는 마지막 행에 붙어 이동하면 된다고 생각했습니다.
첫 번째 행에 최대한 붙는다는 걸 기준으로 했을 때 파이프 라인의 방향 우선순위는 아래와 같습니다.

1. 오른쪽 위
2. 오른쪽
3. 오른쪽 아래

영웅이네 빵집에 파이프라인이 닿았을 경우 해당 파이프 라인이 가장 첫 번째 행렬에 붙어 이동한 경우라 생각하고 해당 행에 대한 탐색은 더 이상 진행하지 않았습니다.

이를 통해 해당 문제는 그리디 문제라는 것을 파악할 수 있었습니다.

2. 코드

첫 번째 시도한 코드였습니다

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

public class Main {
    static int [] nextR = {-1,0,1};
    static int [] nextC = {1,1,1};
    static char [][] pipe;
    static int pipeCount=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int R=Integer.parseInt(st.nextToken())+2;
        int C=Integer.parseInt(st.nextToken());

        pipe = new char[R][C];

        for(int i=1; i<R-1; i++) {
            String s = br.readLine();
            for(int j=0; j<C; j++){
                pipe[i][j] = s.charAt(j);
            }
        }


        for(int i=1; i<R-1; i++) {
            findRoute(i,0);
        }

        System.out.println(pipeCount);

    }

    public static boolean findRoute(int startX, int startY) {
        if(startY==pipe[0].length-1) {
            pipeCount++;
            return true;
        }

        pipe[startX][startY] = 'X';

        boolean check=false;
        for(int i=0; i<3; i++) { //1,0
            if(pipe[startX+nextR[i]][startY+nextC[i]]=='.') {
                check = findRoute(startX+nextR[i], startY+nextC[i]);
            }
            if(!check) continue;
            break;
        }
        return check;
    }
}

통과는 했는데, 해당 코드는 다른 사람들의 코드보다 메모리도 많이 잡아먹는 것 같고 시간도 많이 잡아먹는 것 같아서 코드를 최적화 해보았습니다.
1. string 배열 boolean으로 바꾸기
2. findRoute 함수 최적화
3. 변수명 변경

그래서 최종 코드는 아래와 같습니다.

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

public class Main {
    static int [] dirR = {-1,0,1};
    static int [] dirC = {1,1,1};
    static boolean [][] pipe;
    static int pipeCount=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int R=Integer.parseInt(st.nextToken())+2;
        int C=Integer.parseInt(st.nextToken());

        pipe = new boolean[R][C];

        for(int i=1; i<R-1; i++) {
            String s = br.readLine();
            for(int j=0; j<C; j++){
                pipe[i][j] = s.charAt(j) == '.';
            }
        }

        for(int i=1; i<R-1; i++) {
            findRoute(i,0);
        }

        System.out.println(pipeCount);
    }

    public static boolean findRoute(int startX, int startY) {
        if (startY == pipe[0].length - 1) {
            pipeCount++;
            return true;
        }

        for (int i = 0; i < 3; i++) {
            int nextX = startX + dirR[i];
            int nextY = startY + dirC[i];

            if (pipe[nextX][nextY]) {
                pipe[nextX][nextY] = false;
                if (findRoute(nextX, nextY)) return true;
            }
        }
        return false;
    }

}

시간은 크게 달라지지 않은 것 같습니다. 흠