[99클럽 코테 스터디 5일차 TIL] BFS

📖 오늘의 학습 키워드
BFS

오늘의 회고

문제

[아이템 줍기]
https://school.programmers.co.kr/learn/courses/30/lessons/87694

나의 해결

import java.util.*;
class Solution {
    public int answer;
    public int[][] map;
    public boolean[][] visited;
    public int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        answer = 0;
        map = new int[101][101];
        visited = new boolean[101][101];
        for(int[] points : rectangle){
            int x1 = 2 * points[0];
            int y1 = 2 * points[1];
            int x2 = 2 * points[2];
            int y2 = 2 * points[3];
            for(int y = y1; y <= y2; y++) {
                for(int x = x1; x <= x2; x++) {
                    if(map[y][x] == 2) {
                        continue;
                    }
                    map[y][x] = 2;
                    if(x == x1 || x == x2 || y == y1 || y == y2) {
                        map[y][x] = 1;
                    }
                }
            }
        }
        bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
        return answer/2;
    }
    public void bfs(int characterX, int characterY, int itemX, int itemY) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{characterY, characterX});
        visited[characterY][characterX] = true;
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(now[0] == itemY && now[1] == itemX){
                answer = map[now[0]][now[1]];
                break;
            }
            for(int[] d : directions) {
                int y = now[0] + d[0];
                int x = now[1] + d[1];
                if(x >= 0 && x <= 100 && y >= 0 && y <= 100 && !visited[y][x] && map[y][x] == 1) {
                    q.offer(new int[]{y, x});
                    visited[y][x] = true;
                    map[y][x] = map[now[0]][now[1]] + 1;
                }
            }
        }
    }
}

1. map이라는 이차원 배열을 만들어 테두리 정보를 저장한다.
   • 테두리에는 1을 저장한다.
   • 직사각형의 내부에는 2를 저장한다.
     
   • 입력되는 좌표의 최댓값은 50인데 map의 크기를 100으로 2배한 이유?
     A : 50으로 하는 경우 위 그림처럼 색칠된 부분이 연결된 것처럼 표현돼서 최단경로를 구할 때 영향을 미치게 된다.
     그렇기 때문에 테두리 정보를 저장할 때 직사각형의 모든 좌표값도 2배 곱한다.
2. BFS를 이용해 최단 경로를 찾는다.
   • map 크기를 늘렸기 때문에 캐릭터와 아이템의 좌표도 2를 곱한다.
3. map 크기를 2배 늘렸기 때문에 마지막 정답은 2를 나눈다.

새로 학습한 내용

BFS를 이용해서 최단 경로를 찾는 것은 어렵지 않았으나 처음에 map의 크기를 2배하는 부분에서 많이 헤맸던 것 같다. 앞으로 비슷한 유형의 문제를 만났을 때 당황하지 않고 이러한 아이디어를 바로 떠올려 해결할 수 있었으면 좋겠다.