프로그래머스] 아이템줍기

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

프로그래머스

 

 

 

풀이

2차원배열로 들어오는 직사각형의 정보를 받고,

테두리는 1로 채우고, 내부내용은 2로 채워서 전체 테두리 부분을 구한다.

 

x,y는 y가 2차원배열의 i인덱스 , x가 2차원배열의 j인덱스로 생각하고 진행한다.

 

문제발생 -> 꺾어서 진행해야하는부분이 bfs로 통과할때 문제가 발생함.

꺾어서 내려가야하는데 바로 쭉내려가버림

 

정답은 17인데 안쪽으로 들어갔다나오지않아서 15로 출력됨.

 

 

해결방안 ->  

https://arinnh.tistory.com/88

다른 사람 풀이 -> map을 그릴때 좌표를 각각 2배씩 큰곳에다 그린다. ( 겹쳐서 테두리부분이 잘 안보이는 현상때문에)

x,y 최대 50  좌표씩이였는데 100이라고 가정하고 그린다.

 

즉 원래 도형을 2배크기로 그려준다. 

 

그리고 마지막에 이동횟수를 /2 해준다.

 

 

정답

import java.util.*;
class Solution {
    static int[][] map = new int[101][101];
    static int[] dI = {1, -1, 0, 0};
    static int[] dJ = {0, 0,1,-1};
    static boolean[][] visited = new boolean[101][101];
    static int result =0;
    public static int solution(int[][] rectangle, int characterX, int characterY, int itemX,
        int itemY)    {
        drawMap(rectangle);
//        for (int[] ints : map) {
//            System.out.println(Arrays.toString(ints));
//        }
        bfs(characterX*2, characterY*2, itemX*2, itemY*2);
//        System.out.println(result);
        return result;
    }

    /*
    내부 채우고, 테두리 채우는 로직
    -> y가 2차원 배열의 i인덱스, x가 j인덱스이고,  그려질 전체 그림은 뒤집어진 모양으로 생각

    좌측하단 y ~ 우측상단 y까지 겉의 반복문 반복( i)
    좌측 하단 x ~ 우측상단 x까지 안쪽 반복문 반복 (j)

    i의 첫번째, 마지막은 전부 1로  + j의 첫번째 마지막 인덱스는 1
    */
    static void drawMap(int[][] rectangle)
    {
        for(int[] rect : rectangle)
        {
            int startI = rect[1] *2;
            int endI = rect[3] *2;

            int startJ = rect[0]*2;
            int endJ = rect[2]*2;

            for(int i=startI;i<=endI;i++)
            {
                for(int j=startJ;j<=endJ;j++)
                {
                    if(i == startI || i == endI || j == startJ || j == endJ)
                    {
                        if(map[i][j] ==2)
                        {
                            continue;
                        }
                        map[i][j] = 1;
                    }
                    else{
                        map[i][j] = 2;
                    }
                }

            }


        }


    }
    static void bfs(int characterX, int characterY, int itemX, int itemY)
    {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{characterY, characterX, 0}); //x , y , step

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentI = current[0];
            int currentJ = current[1];
            int currentStep = current[2];

            if (currentI == itemY && currentJ == itemX) {
                result = currentStep/2;
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextI = currentI + dI[i];
                int nextJ = currentJ + dJ[i];

                if(nextI>=1 && nextI <=100 && nextJ>=1 && nextJ <=100)
                {
                    if (!visited[nextI][nextJ] && map[nextI][nextJ] == 1) {
                        visited[nextI][nextJ] = true;
                        q.add(new int[]{nextI, nextJ, currentStep + 1});
                    }
                }

            }
        }

    }

}