프로그래머스 - 아이템 줍기(java)

문제

📃프로그래머스 - 아이템 줍기

DFS/BFS , LEVEL3

코드

    int sx, sy, ex, ey;
    int[][] map = new int[102][102];
    boolean[][] chkMap = new boolean[102][102];
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        sx = characterX * 2;
        sy = characterY * 2;
        ex = itemX * 2;
        ey = itemY * 2;


        /* 1. map에 주어진 사각형 영역을 -1 로 채운다. */
        for(int[] r : rectangle){
            for(int x=r[0]*2; x<=r[2]*2; x++){
                for(int y=r[1]*2; y<= r[3]*2; y++){
                    map[x][y] = -1;
                }
            }
        }

        /* 2. 지뢰찾기 하듯이.. chkMap 에 테두리만 부분만 true 로 남긴다. */
        for(int i=1 ; i< 101 ; i++){
            for(int j=1; j < 101 ; j++){
                if(map[i][j] != -1)continue;
                if(map[i-1][j-1] + map[i-1][j] + map[i-1][j+1] + map[i][j-1] + map[i][j+1] + map[i+1][j-1] + map[i+1][j] + map[i+1][j+1] > -8){
                    chkMap[i][j] = true;
                }
            }
        }

        bfs(sx, sy, 0);

        return map[ex][ey] / 2;
    }


    public void bfs(int x, int y, int cnt){

        if(map[x][y] == -1){
            // map 에 현재 카운트수 기록
            map[x][y] = cnt;

        } else{
            // 이미 방문한 적이 있는 경우(목적지) 더 적은 cnt 채택
            map[x][y] = Math.min(map[x][y], cnt);
        }
        if(x==ex && y==ey ) {
            // 탈출 조건
            return;
        }

        /* 3. 테두리를 따라 갈 수 있는 방향으로 계속 간다. */
        // 목적지를 제외하고 한번 간 곳은 가지 않는다.
        if((x-1 == ex && y == ey) || (chkMap[x-1][y] && map[x-1][y] == -1)) bfs(x-1, y, cnt + 1);
        if((x+1 == ex && y == ey) || (chkMap[x+1][y] && map[x+1][y] == -1)) bfs(x+1, y, cnt + 1);
        if((x == ex && y-1 == ey) || (chkMap[x][y-1] && map[x][y-1] == -1)) bfs(x, y-1, cnt + 1);
        if((x == ex && y+1 == ey) || (chkMap[x][y+1] && map[x][y+1] == -1)) bfs(x, y+1, cnt + 1);

    }

풀이

1. map에 주어진 사각형 영역을 -1 로 채운다.

2. 지뢰찾기 하듯이.. chkMap 에 테두리만 부분만 true 로 남긴다.

3. 테두리를 따라 갈 수 있는 방향으로 간다.

x, y 현재 위치 기준으로 T 인곳으로 가면서 cnt를 map 에 기록한다.

4. 목적지에 있는 cnt 수를 가져온다.

2를 곱하여 계산했으므로 나누기 2 하면 답!