[프로그래머스] Lv3. 아이템줍기 - Java

syeony·2025년 6월 16일
0

Java

목록 보기
16/19

문제 바로가기

접근방식

처음엔 모든 사각형들을 1로 채우고 내부를 0으로 비워서 테두리만 따서 bfs돌리는 방식을 생각했었는데 테스트케이스1~5중 1,5번 틀렸었다.

처음풀이(틀림)

import java.io.*;
import java.util.*;

class 아이템줍기 {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static int answer;

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        answer = 0;
        map=new int[51][51];
        //1로채우기
        for(int i=0;i<rectangle.length;i++){
            int sx=rectangle[i][0];
            int sy=rectangle[i][1];
            int ex=rectangle[i][2];
            int ey=rectangle[i][3];
            for(int x=sx;x<ex+1;x++){
                for(int y=sy;y<ey+1;y++){
                    map[x][y]=1;
                }
            }
            for(int x=sx+1;x<ex;x++){
                for(int y=sy+1;y<ey;y++){
                    map[x][y]=0;
                }
            }
        }

        // for(int i=0;i<11;i++){
        //     System.out.println(Arrays.toString(map[i]));
        // }

        bfs(characterX,characterY,itemX,itemY);
        return answer;
    }

    static void bfs(int characterX, int characterY, int itemX, int itemY){
        visited=new boolean[51][51];
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{characterX,characterY,0});
        visited[characterX][characterY]=true;

        while(!q.isEmpty()){
            int[] c=q.poll();

            if(c[0]==itemX && c[1]==itemY){
                answer=c[2];
                return;
            }

            for(int i=0;i<4;i++){
                int nx=c[0]+dx[i];
                int ny=c[1]+dy[i];
                int dist=c[2];

                if(isEdge(nx,ny)||visited[nx][ny]||map[nx][ny]==0) continue;

                q.offer(new int[]{nx,ny,dist+1});
            }
        }
    }

    static boolean isEdge(int x,int y){
        return x<0||y<0||x>=51||y>=51;
    }
}

나중에 블로그를 찾아보니 모든 범위를 x2해줘야한다고 한다.
왜냐하면 사각형이 여러개 겹쳐있는 경우 테두리도 겹치기 때문에 다른 엉뚱한 테두리를 따라가는 경우가 있기 때문이다.
전체적으로 x2를 해주면 테두리가 분리(?)되기 때문에 괜찮다고한다.

그렇다고함...

정답코드

전체적으로 x2해줘서 마지막에 /2로 정답 출력한 코드

import java.io.*;
import java.util.*;

class 아이템줍기2 {
    static int start_x, start_y, end_x, end_y;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static int answer;

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        //*2하는이유는 겹치는 테두리 제거하기위해서
        start_x=characterX*2;
        start_y=characterY*2;
        end_x=itemX*2;
        end_y=itemY*2;

        answer = 0;
        map=new int[51*2][51*2];

        //1로채우고 내부 0으로 채워서 테두리만 1로.. 구하기
        for(int i=0;i<rectangle.length;i++){
            int sx=rectangle[i][0]*2;
            int sy=rectangle[i][1]*2;
            int ex=rectangle[i][2]*2;
            int ey=rectangle[i][3]*2;
            for(int x=sx;x<ex+1;x++){
                for(int y=sy;y<ey+1;y++){
                    map[x][y]=1;
                }
            }
        }

        for(int i=0;i<rectangle.length;i++){
            int sx=rectangle[i][0]*2;
            int sy=rectangle[i][1]*2;
            int ex=rectangle[i][2]*2;
            int ey=rectangle[i][3]*2;

            for(int x=sx+1;x<ex;x++){
                for(int y=sy+1;y<ey;y++){
                    map[x][y]=0;
                }
            }
        }

        // for(int i=0;i<11;i++){
        //     System.out.println(Arrays.toString(map[i]));
        // }

        bfs();
        return answer;
    }

    static void bfs(){
        visited=new boolean[51*2][51*2];
        Queue<int[]> q=new LinkedList<>();
        visited[start_x][start_y]=true;
        q.offer(new int[]{start_x,start_y,0});

        while(!q.isEmpty()){
            int[] c=q.poll();

            if(c[0]==end_x && c[1]==end_y){
                answer=c[2]/2;
                return;
            }

            for(int i=0;i<4;i++){
                int nx=c[0]+dx[i];
                int ny=c[1]+dy[i];
                int dist=c[2];

                if(isEdge(nx,ny)||visited[nx][ny]||map[nx][ny]==0) continue;

                visited[nx][ny]=true;
                q.offer(new int[]{nx,ny,dist+1});

            }
        }
    }

    static boolean isEdge(int x,int y){
        return x<0||y<0||x>=51*2||y>=51*2;
    }
}

후기

이렇게 전체적으로 범위를 *2로 푸는 bfs문제는 처음 풀어봐서 신선했다. 비슷한 유형 또 나오면 이젠 안틀릴듯(?)

profile
모바일 어플리케이션, cross platform과 iOS에 관심이 많은 개발자 오승연입니다

0개의 댓글