99클럽 코테 스터디 32일차 TIL [DFS, BFS]

- 오늘의 학습 키워드 : DFS, BFS

[문제 이름 : 아이템 줍기 (프로그래머스, Lv 3)]

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

내가 작성한 코드는 아래와 같다.

import java.util.*;

public class Solution {

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        // 좌표 확장
        int[][] board = new int[101][101];

        // 외곽선 표시
        for (int[] rect : rectangle) {
            int x1 = rect[0] * 2;
            int y1 = rect[1] * 2;
            int x2 = rect[2] * 2;
            int y2 = rect[3] * 2;

            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++) {
                    if (i == x1 || i == x2 || j == y1 || j == y2) {
                        if (board[i][j] == 0) {
                            // 외곽선
                            board[i][j] = 1;
                        }
                    } else {
                        // 내부
                        board[i][j] = 2;  
                    }
                }
            }
        }

        // BFS로 최단 거리 탐색
        return bfs(board, characterX * 2, characterY * 2, itemX * 2, itemY * 2);
    }

    private int bfs(int[][] board, int startX, int startY, int targetX, int targetY) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        boolean[][] visited = new boolean[102][102];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY, 0});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int dist = current[2];

            if (x == targetX && y == targetY) {
                return dist / 2;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < 102 && ny < 102 && !visited[nx][ny] && board[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, dist + 1});
                }
            }
        }
        return -1;
    }
}​

[풀이 과정]

지형의 좌표값이 1~50 이므로, 이를 2배로 확장하여 외곽선과 그 내부를 구분하도록 한다. 이때, 두 배를 하게 되면 (1,1)인 경우 (2,2), (50,50)인 경우 (100,100)인데, 경계를 확인하기 위해 101까지 확인하여야 하므로 배열의 크기를 102로 설정해야 한다.

board 배열에 대해서, 아직 처리되지 않은 i,j값이면서 외곽선에 해당하는 부분은 1, 조건에 해당하지 않는 부분은 직사각형 내부에 해당하므로 2로 저장해주었다. 이후, bfs 탐색을 하며 아직 방문하지 않았고, 외곽선에 해당하는 부분에 대하여 너비 우선 탐색을 진행하였다. 이때, 실제 거리의 2배만큼 연산이 진행되므로, 실제 값을 리턴할 때는 다시 2를 나눠주어야 했다.

 

두 배로 확장한다는 아이디어를 떠올리지 못해 시간이 오래걸렸다. 다른 사람의 풀이를 참고하여 코드를 작성하였다.

풀이 시간 : 2시간 30분