99클럽 코테 스터디 32일차 TIL / 아이템 줍기(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 구현

   -  bfs

 

공부한 내용 본인의 언어로 정리하기

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

좌표를 2배로 늘리는 아이디어를 떠올리는게 까다로웠던 bfs 문제를 풀었다.

아이디어만 떠올리면 이후에는 풀만했던 것 같다.

 

풀이 과정은 다음과 같다.

1. 좌표를 2배로 늘림

2. 사각형의 범위를 모두 1로 채움

3. 사각형의 내부를 모두 0으로 바꿈

4. bfs를 통해 1인 경로로만 최단 경로 탐색(1인 경로 = 문제 조건에서의 경로)

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    public int solution(int[][] rectangles, int characterX, int characterY, int itemX, int itemY) {
        
        int[][] map = new int[104][104];
        
        for (int[] rectangle : rectangles) {
            for (int y = rectangle[1] * 2; y <= rectangle[3] * 2; y++) {
                for (int x = rectangle[0] * 2; x <= rectangle[2] * 2; x++) {
                    map[y][x] = 1;  
                }
            }
        }
        
        for (int[] rectangle : rectangles) {
            for (int y = rectangle[1] * 2 + 1; y < rectangle[3] * 2; y++) {
                for (int x = rectangle[0] * 2 + 1; x < rectangle[2] * 2; x++) {
                    map[y][x] = 0; 
                }
            }
        }
        
        int[] dy = {0, 1, 0, -1};
        int[] dx = {1, 0, -1, 0};
        
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[] {characterY * 2, characterX * 2, 0});
        boolean[][] visit = new boolean[104][104];
        visit[characterY * 2][characterX * 2] = true;
        
        while(!que.isEmpty()) {
            int[] cur = que.poll();
            
            if (cur[0] == itemY * 2 && cur[1] == itemX * 2) {
                return cur[2] / 2; 
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                
                if (ny < 0 || nx < 0 || ny >= 104 || nx >= 104) continue;
                if (visit[ny][nx] || map[ny][nx] != 1) continue;
                
                visit[ny][nx] = true;
                que.add(new int[] {ny, nx, cur[2] + 1});
            }
        }
        
        return -1; 
    }
}