백준 : 3109

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

3109번: 빵집

문제를 보다가 최대의 파이프를 설치하는 경우의수는 출발점에서 미로찾기처럼 위쪽벽을 따라서 파이프를 연결하면 된다는 것을 알았다. 이방법으로 로직을 구현했을경우 처음 설계는 처음 출발한 파이프가 벽에 만나서 더이상 나아갈수 없으면 이전까지 방문했던 모든 노드들을 true->false다시 패일로 처리해주고 지나온길을 백트래킹하면서 청소하는 방법을 선택했다. 이런경우 예제에 정답은 나온다.

하지만 제출할경우 시간초과가 발생하였다.
근데 공곰이 생각해본결과 만약 위쪽노드가 실패한 노드를 아래쪽 노드가 그쪽으로 간다고해서 그길을 성공할수가 없다. 따라서 위족노드가 실패한 경로의 방문 경로도 true인채로 그대로해둔다음 소스를 실행하니 AC를 받을수가 있었다.

package com.ssafy.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class 빵집 {
    static int R, C;
    static char[][] map;
    static int dy[] = { -1, 0, 1 };
    static int dx[] = { 1, 1, 1 };
    static int Answer;
    static boolean visit[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }
        
        visit = new boolean[R][C];
        Answer = 0;
        
        for(int r=0;r<R;r++) {
            visit[r][0] = true;
            if(DFS(r,0)) {
                Answer++;
            }else {
                visit[r][0] = false;
            }
        }
        System.out.println(Answer);
 
    }
    public static boolean DFS(int r, int c) {
        if(c == C-1) {
            return true;
        }
        
        for(int d=0;d<3;d++) {
            int ny = r+dy[d];
            int nx = c+dx[d];
            if(ny<0||ny>=R)continue;
            if(map[ny][nx]=='x')continue;
            if(visit[ny][nx]) continue;
            
            visit[ny][nx] = true;
            if(DFS(ny,nx)) {
                return true;
            }
//            시간초과 발생 코드
//            else {
//                visit[ny][nx] =false;
//            }
            
        }
        return false;
        
    }
}