Baekjoon[3109] - 빵집

링크

 

3109번: 빵집

 

문제설명

• DFS+그리디

문제풀이

• DFS+그리디

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main3109 {
    public static int[][] map;
    public static int[][] dir = {
            {-1,1},    //우상
            {0,1},    //우
            {1,1}    //우하
    };
    public static int R;
    public static int C;
    public static int Ans=0;
    public static boolean chk;
    public static void DFS(int[] rc) {
        int nr=0;
        int nc=0;
        if(chk) {    // 이미 도달했었으면 나머지 탐색안함.
            return;
        }
        if(rc[1]==C-1) {    //끝에 도달한 것.
            Ans++;
            chk=true;
            return;
        }

        for (int i = 0; i < 3; i++) {
            nr = rc[0] + dir[i][0];
            nc = rc[1] + dir[i][1];
//            경계 안이고 & 갈 수 있을 경우            
            if(nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc]==0 && !chk) {
                map[nr][nc]=1;
                DFS(new int[] {nr,nc});
            }
        }
//        길이없다
        return;
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/3109.txt"));
        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 int[R][C];
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                if(line.charAt(j)=='.')map[i][j]=0;
                else map[i][j]=1;
            }
        }

        for (int i = 0; i < R; i++) {
            chk=false;
            DFS(new int[] {i,0});
        }

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• 가지치기 할 때, 끝에 도달했을때를 chk하는 것 신경안씀
  • 끝에 도달했을 가지만 chk넣었었음
  • 호출된 모든 가지들에 대해서 chk할 수 있도록 DFS호출 전에 chk넣어야 함.
  • 그리디하게 갔다가 막혔을 경우를 생각안했었음.얻어걸림
    • 이부분은 막혔기때문에 어차피 그길로 가면 안되기때문에 visit처리 해놓는게 맞음.
    • 안하면 밑으로갔다가 위로가서 다시 가기때문에 시간초과 뜸

잘한점

• 그리디 접근 (우상>우>우하)
• 가지치기 할 생각은 함
• char 배열을 int로 바꿨음