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

짱챌·2025년 5월 7일

BFS 프로그래머스

Algorithm

목록 보기

11/19

📌 문제 정보

[Lv3. 아이템줍기]

💡 접근 방식

좌표를 2배로 늘려서 생각한다.

정수 좌표를 다룰 때, 코너링을 처리하기 위해서는 좌표를 2배로 늘려서 풀어야 한다!

무슨 말이냐면,, ㄷ자로 된 길이 있다고 생각해보자. 우측 아래에서 출발한다고 가정하면
좌 -> 상 -> 우가 당연한 루트로 보이겠지만
우리의 프로그램은 ㄷ을 ㅁ처럼 생각한다..
우측 아래에서 바로 상으로 가는 엄청난 길을 개척할 것이다.
왜냐면? 도달 가능한 곳(board[][] == 1)이고 안가봤을테니까(visited[][] == false)

이를 막기 위해 좌표를 2배로 늘리는 것이다~!

( 내 글이 이해가 잘 안된다면 다음 글이 도움이 될 것이다 ㅎㅎ)
https://taehoung0102.tistory.com/95

✅ 코드

import java.util.*;

class Solution {
    static int[][] board;
    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) {
        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 2;
        answer = 0;
        
        board = new int[102][102];
        visited = new boolean[102][102];
        
        for (int[] rec: rectangle){
            
            for(int i= rec[0]*2; i<=rec[2]*2; i++){
                if(board[i][rec[1]*2] != 2) board[i][rec[1]*2] = 1;
                if(board[i][rec[3]*2] != 2) board[i][rec[3]*2] = 1;
            }
            for(int i= rec[1]*2; i<=rec[3]*2; i++){
                if(board[rec[0]*2][i] != 2) board[rec[0]*2][i] = 1;
                if(board[rec[2]*2][i] != 2) board[rec[2]*2][i] = 1;
                
            }
            for(int i= rec[0]*2 +1; i<rec[2]*2; i++){
                for(int j= rec[1]*2 + 1; j< rec[3]*2; j++){
                    board[i][j] = 2;
                }
            }

            
        }
        
        bfs(characterX, characterY, itemX, itemY);
        
        return answer;
    }
    
    public static void bfs(int x, int y, int itemX, int itemY){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y, 0});
        visited[x][y] = true;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            
            if(cur[0] == itemX && cur[1] == itemY){
                answer = cur[2] / 2;
                return;
            }
            
            for (int i=0; i<4; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                
                if(nx >=0 && nx <=101 && ny >=0 && ny<=101){
                    if (board[nx][ny] == 1 && !visited[nx][ny]){
                        q.add(new int[]{nx, ny, cur[2] + 1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
        
}