인프런 JAVA 알고리즘 정리(DFS, BFS 활용 8~15번)

 

<Error>

<Code>AccessDenied</Code>

<Message>Access Denied</Message>

<RequestId>7VKㄹㄷ7ㄹㄹBS6FQ704K885</RequestId>

<HostId>qIEAFwzuh+2t2fNXlzFm6QdvDF27FjvRN9nj2hacWFKfOatXaZ3PPoFx/vSRNTt10d60TRXD/nw=</HostId>

</Error>

8. ⭐수열 추측하기⭐

// 1부터 N 까지의 숫자가 한 개씩 적혀있는데 그 숫자를 추측해라.

// N이 4라고 하고 마지막 값이 16이 주어진다면

3 1 2 4 가 답

맨 위의 숫자는? 여러 값이 있다면 가장 앞에 오는 것을 출력

 

조합을 먼저 구하고 -> 순열를 바꿔가며 재귀를 돈다.

4 의 값 (3*1)  + (1*3) +  (2*3) + (4*1) = 16  규칙이 존재 4자리수면 1 3 3 1 을 곱하는 최종 결과라는...

5자리면 1 4 6 4 1 

 

1. 1 3 3 1  <- 배열에 이 값을 저장 3C0, 3C1, 3C2, 3C3 을 구해주는 함수 필요 // 이 패턴을 아는게 핵심

for(int i=0; i<n; i++){
    b[i] = T.combi(n-1, i);
}

public int combi(int n, int r){
    if(dy[n][r]>0) return dy[n][r];
    if(n==r || r==0) return 1;
    else return dy[n][r] = combi(n-1, r-1)+combi(n-1,r);
}

 -> b { 1, 3, 3, 1 } 

 

2. 순열을 돌며 최종값이 16인것을 찾는다.

 중복 순열이 아니기에 ch배열로 중복값 무시 작업

public void DFS(int L, int sum){
    if(flag) return;
    if(L == n){
        if(sum==f){
            for(int x : p) System.out.print(x+" ");
            flag = true;
        }
    }
    else{
        for(int i=1; i<=n; i++){
            if(ch[i]==0){
                ch[i]=1;
                p[L]=i;
                DFS(L+1, sum+(p[L]*b[L]));
                ch[i]=0;
            }
        }
    }
}

1 1 1 1 ~ 4 4 4 4 지만 중복값이 제거 되니 1 2 3 4 부터 시작해서 4 3 2 1 까지 최종값이 16이면 종료

 

 

 

9. 조합 구하기 

// 1~N까지 번호가 적힌 구슬이 있고 이 중 M개를 뽑는 방법의 수를 출력

public void DFS(int start, int Level) {
    if (Level == L) {
        for (int x : arr) if (x != 0) System.out.print(x + " ");
        System.out.println();
    } else {
        // 조합 
        for (int i = start; i <= n; i++) {
            arr[Level] = i;
            DFS(i + 1, Level + 1);
        }
    }
}

 

 

10. 미로탐색 (DFS)

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.

격자판의 움직임은 상하좌우로만 움직인다.

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

static int[][] arr;
static int[] listy = {1, 0, -1, 0};
static int[] listx = {0, 1, 0, -1};
static int sum = 0;
public void DFS(int x, int y) {
    if (x == 6 && y == 6) {
        sum++;
        return;
    }
    // 규칙에 어긋나면 RETURN
    if (x > 6 || y > 6 || x < 0 || y < 0 || arr[x][y]==1 ) {
        return;
    } else {
        arr[x][y]=1; // 이미 간 지점은 다시 못감
        for (int i = 0; i < 4; i++) {
            DFS(x + listx[i], y + listy[i]);
        }
        arr[x][y]=0; // 다 돌았으면 갈 수 있게 풀어준다.
    }
}

public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);

    arr = new int[7][7];

    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            arr[i][j] = kb.nextInt();
        }
    }
    T.DFS(0, 0);
    System.out.println(sum);
}

 

 

11. 미로의 최단거리 통 (BFS)

도착까지 갈 수 있는 최단거리는 12

static int[][] arr;
static int[] listy = {1, 0, -1, 0};
static int[] listx = {0, 1, 0, -1};

public int BFS() {
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(0,0));
    int level=1;

    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i=0; i<size; i++){
            Point point = queue.poll();
            arr[point.x][point.y]=1;
            for(int j=0; j<4; j++){
                int x = point.x+listx[j];
                int y = point.y+listy[j];
                if(x==6 && y==6) return level;
                if(x>=0 && x<7 && y>=0 && y<7 && arr[x][y]==0) {
                    queue.add(new Point(x,y));
                }
            }
        }
        level++;
    }
    return -1;
}

public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);

    arr = new int[7][7];

    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            arr[i][j] = kb.nextInt();
        }
    }
    System.out.println(T.BFS());

}

public class Point {
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y= y;
    }
}

 

 

12. 토마토 (BFS 활용)

public int BFS(int [][]arr) {
    Queue<Point> queue = new LinkedList<>();
    for(int i=0; i<arr.length; i++){
        for(int j=0; j<arr[i].length; j++){
            if(arr[i][j]==1)  queue.add(new Point(i,j));
        }
    }
    int level=0;

    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i=0; i<size; i++){
            Point point = queue.poll();

            for(int j=0; j<4; j++){
                int x = point.x+listx[j];
                int y = point.y+listy[j];

                if(x>=0 && x<arr.length && y>=0 && y<arr[0].length && arr[x][y]==0) {
                    queue.add(new Point(x,y));
                    arr[x][y]=1;
                }
            }
        }
        if(!queue.isEmpty())level++;
    }
    // while문을 돌았지만 익지않은 토마토가 있다? 그럼 -1 리턴
    for(int[] x: arr){
        for(int y : x){
            if(y==0) return -1;
        }
    }
    return level;
}

 

13. 섬나라 아일랜드

1이 섬 ( 대각선도 하나의 섬으로 연결) 이 지도의 섬은 5개

static int arrnum;
static int[][] arr;
static int[] listy = {1, 1, 0, -1,-1, -1, 0, 1};
static int[] listx = {0, 1, 1, +1, 0,-1, -1, -1};

public void DFS(int x, int y) {
    if(x<0 || x>arrnum-1 || y>arrnum-1 || y<0 || arr[x][y]==0){
        return ;
    }else{
        arr[x][y]=0;
        for(int i=0; i<8; i++){
            DFS(x+listx[i], y+listy[i]);
        }
    }

}

public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);


    arrnum = kb.nextInt();

    arr = new int[arrnum][arrnum];


    for (int i = 0; i < arrnum; i++) {
        for (int j = 0; j < arrnum; j++) {
            arr[i][j] = kb.nextInt();
        }
    }
    int cnt =0;
    for(int i=0; i<arr.length; i++){
        for(int j=0; j<arr.length; j++){
            if(arr[i][j]==1) {
                cnt++; // 육지 발견
                T.DFS(i,j); // 발견된 육지를 0으로 변경작업 
            }
        }
    }
    System.out.println(cnt);

}

 

14. 섬나라 아일랜드(BFS)

 

// 12번과 거의 유사

 

 

 

15. 피자 배달 거리 (삼성 SW역량평가 기출문제 : DFS활용)

 

1. 피자집들의 조합을 먼저 구하라. (6개의 피자집중 4개를 선택)

2. 조합들을 바탕으로 집집마다 거리를 측정

3. 조합을 바탕으로 측정한 거리중 가장 작은 거리 선정

static int n,m,len, answer = Integer.MAX_VALUE;
static int[] combi;
static ArrayList<Point> hs, pz;


public void DFS(int L, int s){
    if(L==m){ // 조합을 바탕으로 거리를 측정
        int sum=0;
        for(Point h : hs){
            int dis = Integer.MAX_VALUE;
            for(int i: combi){
                dis = Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y));
            }
            sum += dis;
        }
        answer = Math.min(answer, sum);

    } //조합 구하기 (암기 필수) 1 2 3 4 / 1 2 3 5 / 1 2 3 6 ...
    else{
        for(int i=s; i<len; i++){
            combi[L] = i;
            DFS(L+1, i+1);
        }
    }

}


public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    n = kb.nextInt();
    m = kb.nextInt();
    pz = new ArrayList<>();
    hs = new ArrayList<>();
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int tmp = kb.nextInt();
            if(tmp==1) hs.add(new Point(i, j));
            else if(tmp==2) pz.add(new Point(i,j));
        }
    }
    len = pz.size();
    combi = new int[m];
    T.DFS(0,0);
    System.out.println(answer);

}
public static class Point {
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y= y;
    }
}