[백준/JAVA] 16973번: 직사각형 탈출

📖 문제

16973번: 직사각형 탈출

 

 

💡  풀이 방식

• BFS

- 벽 위치를 저장받는 리스트를 생성해 벽 위치를 저장한다. → 나중에 사각형 범위 안에 벽이 있는지 확인할 때 사용하기 위함

- 시작점 (Sr, Sc)에서부터 인접한 상하좌우 칸으로 이동하며 BFS를 수행한다.

  ┕ 큐에 저장할 값 :  (행, 열, 이동 거리)

  ┕ 현재 점의 위치가 목표 위치 (Fr,Fc)에 도달했다면, 현재까지의 이동 거리를 출력하고 종료한다.

  ┕ 목적지에 도달하지 못 했다면, 상하좌우를 탐색해 이동 가능한 곳으로 이동하며 방문 표시도 하고, 이동 거리를 갱신한다.

         → 이동 가능 조건 : 격자 범위 내에 있고, 방문한 적 없고, 벽(1)이 아니어야 하며, 해당 범위 내에 벽(1)이 존재해선 안 된다.

 

 

 

💥 유의사항

시간 초과

해당 사각형 범위 내에 벽이 존재하는지 확인하고자 매번 N*M만큼 연산을 하면 시간초과가 난다...

// 매번 사각형이 범위 안에 있거나 사각형 안에 벽이 있는지 확인하면 시간초과 남
for(int i = r ; i < r + H ; i++) {
    for(int j = c ; j < c + W ; j++) {
        if(!inRange(i, j) || grid[i][j] == 1)
            return false;
    }
}

 

이를 해결하려면, 벽의 위치를 리스트에 넣고, 벽의 위치가 r ~ r+H, c ~ c+W 범위에 있다면 직사각형 안에 벽이 있는 것이므로 유효성 검사에서 false를 반환하면 된다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N, M;
    static int H,W,sr,sc,fr,fc;
    static int[][] grid;
    static boolean[][] visited;
    
    static List<int[]> wallList = new ArrayList<>();    // 🔔 벽 위치 저장 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        grid = new int[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1];
                
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= M ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                
                if(grid[i][j] == 1)
                    wallList.add(new int[] {i, j});
            }
        }
        
        st = new StringTokenizer(br.readLine(), " ");
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        sr = Integer.parseInt(st.nextToken());
        sc = Integer.parseInt(st.nextToken());
        fr = Integer.parseInt(st.nextToken());
        fc = Integer.parseInt(st.nextToken());
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {sr, sc, 0});
        visited[sr][sc] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            // 목표 위치 도달하면 탐색 종료
            if(now[0] == fr && now[1] == fc) {
                return now[2];
            }
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                // 범위와 방문 여부 확인
                if(!inRange(nx, ny) || visited[nx][ny] || grid[nx][ny] == 1)    continue;
                
                // 사각형 범위와 벽 있는지 확인
                if(!isPossible(nx, ny)) continue;
                
                q.add(new int[] {nx, ny, now[2] + 1});
                visited[nx][ny] = true;
            }            
        }
        
        return -1;
    }
    
    private static boolean inRange(int r, int c) {
        return (1 <= r && r <= N && 1 <= c && c <= M);
    }
    
    // 🔔 사각형이 존재하는지 확인하는 메소드
    private static boolean isPossible(int r, int c) {
        // 사각형이 범위 벗어나면 false
        if(r + H - 1 > N || c + W - 1 > M)  return false;
        
        // 벽 위치를 순서대로 꺼내 사각형 범위 안에 있는지 확인
        for(int i = 0 ; i < wallList.size() ; i++) {
            int[] wall = wallList.get(i);
            
            if(r <= wall[0] && wall[0] < r + H && c <= wall[1] && wall[1] < c + W)
                return false;
        }
        
        return true;
    }
}
 

 

 

 

---

💦 어려웠던 점

- 로직은 어렵지 않았는데 시간초과 문제가 해결이 안 되어서 너무나도 답답하였다...

 

백준 16973 시간초과 검색해서 다른 분들이 작성해주신 이유를 통해 왜 시간 초과가 떴는지 확인할 수 있었다...

담엔 시간 복잡도 계산을 제대로 하고 진행하도록 하자..

 

 

🧐 새로 알게 된 내용

BFS에서 이동 횟수 출력할 때 따로 전역변수를 활용하지 않고 바로 int형으로 출력하게 한 점!

목적지면 바로 현재까지의 이동 횟수 출력하게 하고, 목적지까지 가지 못 했다면 -1 출력하게 해서 결과 받기.. 이게 전역 변수 만들고 갱신하는 것보다 훨씬 나한테 잘 편하다고 생각되었다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

velog

 

[백준] 16973 직사각형 탈출 - BFS JAVA

 

백준 16973번 : 직사각형 탈출 (Java)