99클럽 코테 스터디 13일차 TIL: [프로그래머스] 아이템 줍기

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

프로그래머스

 

bfs 문제인 건 딱 보고 알았는데 구현을 어떻게 해야할지 감이 안왔다. 주의할 점들은 다음과 같다.

• 우선 내가 막힌 부분은 "테두리를 의미하는 꼭짓점을 이차원 배열로 구현하는 것이 올바른가?"였다. 그런데 다음을 보면, 테두리를 기준으로 해서 테두리 수를 셌을 때랑, 이차원 배열을 기준으로 해서 가장자리 칸들의 수를 셌을 때랑 차이가 없다는 것을 알 수 있다. 따라서 이차원 배열로 구현해도 된다!

• 다음으로는 배열 크기를 두배로 만들어주고 시작점과 끝점도 두배를 해줘야 한다. 그 이유는 입출력 예 1번을 보면 알 수 있다. 입출력 예 1번에서 (x, y)가 (3, 4)일 때 (3, 6)으로 갈수도 있고, (4, 5)로 갈수도 있다. 그런데 사실 (3, 6)은 테두리가 아닌데 이를 코드 상에서 제어할수가 없다. 따라서 배열을 두배로 늘려주면 이를 제어할 수 있다.
• 그리고 두배로 늘린 배열에 값을 채운 뒤 bfs를 진행하면 된다. 테두리면 2, 사각형의 내부이면 1을 채웠다. 이때 주의할 점은 이미 1인 값은 계속 1이어야 한다(두 사각형이 겹칠 때, 이미 한 사각형의 내부라서 1이면 다른 사각형의 테두리라고 하더라도 전체적으로는 내부이기 때문). 그리고 이미 2인 값은 1이 될 수 있다(한 사각형의 테두리라서 2라고 하더라도, 다른 사각형과 겹쳐지면서 전체적으로 내부가 될 수 있기 때문).

import java.util.*;

class Solution {
    
    int[][] map = new int[101][101];
    boolean[][] visited = new boolean[101][101];
    int[][] cnt = new int[101][101];
    int answer = 0;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        for (int[] r : rectangle) {
            fillMap(r[0] * 2, r[1] * 2, r[2] * 2, r[3] * 2);
        }
        
        bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
        
        return answer / 2;
    }
    
    public void fillMap(int x1, int y1, int x2, int y2) {
        for (int i = y1; i <= y2; i++){
            for (int j = x1; j <= x2; j++) {
                // 이미 1이면 계속 1이어야 함
                if (map[i][j] == 1) {
                    continue;
                }
                
                if (i == y1 || i == y2 || j == x1 || j == x2) {
                    map[i][j] = 2;
                } else {
                    // 이미 2(테두리)여도 덮여서 1이 될 수 있음
                    map[i][j] = 1;
                }
            }
        }
    }
    
    public void bfs(int startX, int startY, int endX, int endY) {
        
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(startY, startX));
        visited[startY][startX] = true;
        
        while (!que.isEmpty()) {
            if (cnt[endY][endX] != 0) {
                answer = cnt[endY][endX];
                break;
            }
            Node now = que.poll();
            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + now.y;
                int nx = dx[i] + now.x;
                
                if (nx < 0 || nx > 100 || ny < 0 || ny > 100) continue;
                if (visited[ny][nx] || map[ny][nx] != 2) continue;
                
                que.add(new Node(ny, nx));
                visited[ny][nx] = true;
                cnt[ny][nx] = cnt[now.y][now.x] + 1;
            }
        }
    }
    
    public class Node {
        
        int y, x;
        
        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

bfs 자체는 쉽지만, 구현 아이디어를 떠올리는 것과 주의 사항을 체크하는 것이 아직 부족하다.