코테 연습[자바 코테 준비 9일차] bfs 완탐(2)

목표 :  카카오 2022 블라인드 양궁 문제를 빠르게 풀자

 

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

 

풀기 전 빌드업을 위해 bfs 를 푼다.

 

알고리즘  기본 최단 거리 길찾기 문제이다 .

return 으로 최단 거리를 보여주면 된다. 

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

1. 4반향을 확인한다 .

2. 갈수 있으면 이동  , 현위치 거리 +1 을 한 결과와 지점에서의 거리를 비교 , 

int map[y][x] 로 고정하여 생각한다. 

 

 

public int solution2(int[][] maps) {
    int y = maps.length;
    int x = maps[0].length;

    if( x == 1 && y == 1) {
        if(maps[0][0] == 0 ) return  -1;
        else return 1 ;
    }
    if(maps[0][1] == 0 && maps[1][0] == 0 ) return  -1 ;


    int inf = Integer.MAX_VALUE;

    int[][] way = {{1,0},{0,1},{-1,0},{0,-1}};

    int[][] cost = new int[y][x];
    for(int j = 0 ; j < y ; j++ ) {
        for(int i = 0 ; i < x ; i++ ) {
            if(maps[j][i] == 1) cost[j][i] = inf ;
        }
    }
    boolean[][] visit  = new boolean[y][x] ;

    cost[0][0] = 1 ;

    Queue<String> q = new LinkedList<>();

    String start = "0:0" ; // x : y : value
    visit[0][0] = true;
    q.offer(start);

    while(!q.isEmpty()) {
        String[] currCord = q.poll().split(":");// split and int parse
        int currX = Integer.parseInt(currCord[0]);
        int currY = Integer.parseInt(currCord[1]);
        int currCost = cost[currY][currX];
            for(int i = 0 ; i < 4 ; i++ ) {
                int nx =currX+way[i][0];
                int ny =currY+way[i][1];
                if(check(maps,visit,x,y,nx,ny)) {
                    String item = nx +":"+ ny;
                    visit[ny][nx] = true;
                    q.offer(item);
                    if(currCost + 1 < cost[ny][nx]) {
                        cost[ny][nx] = currCost +1 ;
                    }
                }
            }
    }
    if(visit[y-1][x-1]) return  cost[y-1][x-1];
    return -1 ;

}
public boolean check(int[][] maps ,boolean[][] visit ,int maxX ,int maxY , int currX , int currY) {
    if( maxX <= currX || currX <=-1 || maxY <= currY || currY <=-1 ){
        return false ;
    }
    if(maps[currY][currX] == 0)return false;

    if(visit[currY][currX])return false;

    return true;
}

 

 

 

 

---> 함수를 인라인으로 만들고 불필요한 파싱을 제외한 코드 이다. 

public int solution(int[][] maps) {
    int y = maps.length;
    int x = maps[0].length;

    int[][] way = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    int[][] cost = new int[y][x];
    for (int[] row : cost) {
        Arrays.fill(row, -1);
    }

    cost[0][0] = 1;

    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0});

    while (!q.isEmpty()) {
        int[] currCord = q.remove();
        int currX = currCord[0];
        int currY = currCord[1];
        int currCost = cost[currY][currX];

        for (int i = 0; i < 4; i++) {
            int nx = currX + way[i][0];
            int ny = currY + way[i][1];

            if (nx >= 0 && nx < x && ny >= 0 && ny < y && maps[ny][nx] == 1 && cost[ny][nx] == -1) {
                cost[ny][nx] = currCost + 1;
                q.offer(new int[]{nx, ny});
            }
        }
    }

    return cost[y - 1][x - 1];
}

 

 

 

 

카카오 2022 블라인드 양궁 문제 

직접 작성한 솔류션이 아닌 기존에 돌아다니는 솔류션을 가지고왔다.  dfs 를 사용한 접근 방식이다.

@Test
void sol21() {
    int[] given = pr.parseIntegerList("[2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]");
    int n = 5;
    solution10(n,given);
}
public  ArrayList<int[]> list = new ArrayList<int[]>();
public  int max_diff = -1;
public  int[] ryan;
public  int[] apeach;
public int[] solution10(int n, int[] info) {
    int[] answer = {} ;
    ryan = new int[11];
    apeach = info;
    dfs_sol10(n,0,0);
    if(max_diff == -1) return new int[]{-1};
    Collections.sort(list, (o1, o2) -> {
        for(int i=10;i>=0;i--){
            if(o1[i] != o2[i]) return o2[i] - o1[i];
        }
        return 0;
    });

    return list.get(0);
}
public void dfs_sol10(int n , int depth,int start){
    if(depth == n){
        int a_sum = 0 ;
        int r_sum = 0 ;
        for(int i = 0 ; i <10 ; i++){
            if(apeach[i] == 0 && ryan[i] == 0) continue;
            if(apeach[i] >= ryan[i]) a_sum += (10-i);
            else r_sum += (10-i);
        }

        if(r_sum > a_sum){
            int diff = r_sum - a_sum;
            if(max_diff < diff){
                max_diff = diff;
                list.clear();
                list.add(ryan.clone());
            } else if(max_diff == diff){
                list.add(ryan.clone());
            }
        }

        return;
        }

    for(int i=start;i<11;i++){
        ryan[i]++;
        dfs_sol10(n, depth+1, i);
        ryan[i]--;
    }
}