[백준] 3109 빵집 - Java

 

 

 

파이프를 가장 많이 연결하기 위해서는..

 

1. 첫 번째 행 부터 탐색한다.

2. 다음 열을 탐색 할 때는  ↗ →  ↘ 순서로 탐색해야 한다. (그리디)

3. 파이프를 겹쳐서 설치하면 안되니, 방문 처리를 확실하게 해 주자.

 

탐색 순서가 정해져 있기 때문에, 탐색 시 bfs를 사용하면 안 된다.

 

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int R, C;
    static char[][] map;
    static boolean[][] visit;
    static int[] dr = {-1,0,1};
    static int[] dc = {1,1,1};

    static int ans = 0;
    static boolean flag = false;

    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];
        visit = new boolean[R][C];

        for(int i=0; i<R; i++){
            String str = br.readLine();
            for(int j=0; j<C; j++){
                map[i][j] = str.charAt(j);
            }
        }

        for(int i=0; i<R; i++){
            flag = false;
            dfs(i,0);
        }

        System.out.println(ans);    
        
    }

    static void dfs(int r, int c){
        visit[r][c] = true;

        if(c == C - 1){
            ans++;
            flag = true;
            return;
        }

        for(int i=0; i<3; i++){
            int nextR = r + dr[i];
            int nextC = c + dc[i];

            if(nextR >= R || nextR <= -1 || nextC >= C || nextC <= -1) continue;
            if(map[nextR][nextC] == 'x') continue;
            if(visit[nextR][nextC]) continue;

            dfs(nextR, nextC);

            if(flag) return;
        }
    }
}

 

 

첫 번째 행에서 출발해서 마지막 열에 한 번 도착했으면 더 이상 파이프를 설치하면 안 된다.

flag 변수를 통해서 이 부분을 처리해줬다.

 

나머지는 위의 1 2 3 을 지키도록 작성했다.