[프로그래머스/Level 3] 아이템 줍기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS

 

1. 범위를 2배로 늘려 0~100 으로 격자 크기를 늘린 2차원 int형 배열을 생성한다.

int[][] board = new int[101][101];

 

→ Why? 선이 아닌 좌표를 기준으로 하므로 크기를 2배로 확장해야 제대로 탐색을 할 수 있기 때문이다. (참고)

 

 

2. rectangle 배열을 돌며, 내부와 테두리를 구분해 위에서 만든 배열에 값을 저장해준다. (여기서도 2배해준 값 사용하기)

for(int[] r : rectangle) {
    fill(2*r[0], 2*r[1], 2*r[2], 2*r[3]);
}

private static void fill(int x1, int y1, int x2, int y2) {
    for(int i = x1 ; i <= x2 ; i++) {
        for(int j = y1 ; j <= y2 ; j++) {
            if(board[i][j] == 2)    continue;

            // 내부
            board[i][j] = 2;

            // 테두리값
            if(i == x1 || i == x2 || j == y1 || j == y2)
                board[i][j] = 1;
        }
    }
}

 

 

3. 캐릭터 위치부터 BFS 탐색을 통해 캐릭터 위치부터 각 좌표까지의 최소 이동거리를 계산한다. (좌표 간 최소 이동거리 계산)

Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {sx, sy});	// [시작점] 캐릭터 위치

int[][] dist = new int[101][101];   // 방문 여부 & 이동 거리 저장용 배열 (0: 미방문)
dist[sx][sy] = 1;   // 방문 처리 & 이동 거리 저장

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

    for(int d = 0 ; d < 4 ; d++) {	//
        int nx = now[0] + dx[d];
        int ny = now[1] + dy[d];

        if(!inRange(nx, ny))    continue;

        if(board[nx][ny] == 1 && dist[nx][ny] == 0) {
            dist[nx][ny] = dist[now[0]][now[1]] + 1;    // 방문 처리 & 이동 거리 갱신
            q.add(new int[] {nx, ny});
        }
    }
}

 

 

4. 아이템 위치에서의 이동 거리를 2로 나눈 값을 정답으로 출력한다. (값을 2배 늘려줬으므로 원상복구)

answer = dist[ex][ey] / 2;

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int[][] board;
    static int answer;
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        board = new int[101][101];  // 격자 크기를 2배로 늘리기
                
        for(int[] r : rectangle) {
            fill(2*r[0], 2*r[1], 2*r[2], 2*r[3]);
        }
                
        bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);
        return answer;
    }
    
    // 내부와 테두리 구분하는 메소드
    private static void fill(int x1, int y1, int x2, int y2) {
        for(int i = x1 ; i <= x2 ; i++) {
            for(int j = y1 ; j <= y2 ; j++) {
                if(board[i][j] == 2)    continue;
                
                board[i][j] = 2;    // 내부
                
                // 테두리값 구분하기
                if(i == x1 || i == x2 || j == y1 || j == y2)
                    board[i][j] = 1;
            }
        }
    }
    
    private static void bfs(int sx, int sy, int ex, int ey) {        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {sx, sy});
        
        int[][] dist = new int[101][101];   // 방문 여부 & 이동 거리 저장용 배열 (0: 미방문)
        dist[sx][sy] = 1;   // 방문 처리
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
                        
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny))    continue;
                
                if(board[nx][ny] == 1 && dist[nx][ny] == 0) {
                    dist[nx][ny] = dist[now[0]][now[1]] + 1;    // 방문 처리 & 이동 거리 갱신
                    q.add(new int[] {nx, ny});
                }
            }
        }
        
        answer = dist[ex][ey] / 2;  // 격자 크기 2배 했으므로 2 나눠주기
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x <= 100 && 0 <= y && y <= 100);
    }
}

 

 

 

➕ 다른 풀이 방식

- 내가 풀려고 했던 방식! 이동 횟수를 큐에 저장해서 푸는 방식.

그리고 테두리 구분하는 방식이 조금 다르다.

[프로그래머스] 위클리 챌린지 11주차 아이템 줍기 (Java)

 

---

💦 어려웠던 점

- 이동 횟수를 큐에 저장해서 하려고 생각했었다. (이 방법으로도 해결할 수 있긴 하다.)

- 격자 크기를 2배로 늘릴 생각을 하지 못 했다.

 

🧐 새로 알게 된 내용

- 격자 크기를 2배로 늘려야 하는 이유

- 테두리 필터링 방식!!

private static void fill(int x1, int y1, int x2, int y2) {
    for(int i = x1 ; i <= x2 ; i++) {
        for(int j = y1 ; j <= y2 ; j++) {
            if(board[i][j] == 2)    continue;

            board[i][j] = 2;    // 내부

            // 테두리값 구분하기
            if(i == x1 || i == x2 || j == y1 || j == y2)
                board[i][j] = 1;
        }
    }
}

 

 

 

- 이동 횟수를 큐에 저장하기 vs 이동 거리 배열에 값 저장하기... 그냥 찾아봤다

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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