Baekjoon[16973] - 직사각형 탈출

링크

16973번: 직사각형 탈출

문제설명

• 직사각형을 벽을 피해서 이동하며 경로찾기

문제풀이

• 직사각형 이동 가능성 검사하면서 BFS
  • 갈수 없는 부분을 움직이면서 체크하기 -> 체크 다 한 후 움직이기

문제코드

package baekjoon;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main16973 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int N;
    public static int M;
    public static int[][] map;
    public static int[][] visited;

    public static int H;
    public static int W;
    public static int sr;
    public static int sc;
    public static int fr;
    public static int fc;

    public static void mark(int r, int c) {

        for (int i = r-(H-1); i <= r; i++) {
            for (int j = c-(W-1); j <= c; j++) {
                if(i>=0 && i<N && j>=0 && j<M) {
                    visited[i][j]=1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/16973.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        map=new int[N][M];
        visited=new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken()); 
        W = Integer.parseInt(st.nextToken()); 
        sr= Integer.parseInt(st.nextToken())-1; 
        sc= Integer.parseInt(st.nextToken())-1; 
        fr= Integer.parseInt(st.nextToken())-1; 
        fc= Integer.parseInt(st.nextToken())-1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j]==1) {
                    mark(i,j);
                }
            }
        }

        LinkedList<int[]> q = new LinkedList<int[]>();

        q.add(new int[] {sr,sc});
        visited[sr][sc]=1;

        int qs;
        int[] now;
        int nr;
        int nc;
        int len=0;
        boolean fin=false;
        top:
        while(!q.isEmpty()) {
            qs = q.size();
            for (int i = 0; i < qs; i++) {
                now = q.poll();
                if(now[0]==fr && now[1]==fc) {
                    fin=true;
                    break top;
                }
                for (int d = 0; d < 4; d++) {
                    nr = now[0] + dir[d][0];
                    nc = now[1] + dir[d][1];
                    if(nr>=0 && nr<N-H+1 && nc>=0 && nc<M-W+1 && visited[nr][nc]==0) {
                        q.add(new int[] {nr,nc});
                        visited[nr][nc]=1;
                    }
                }
            }
            len++;
        }

        if(fin) {
            System.out.println(len);
        }
        else {
            System.out.println(-1);
        }
    }
}

아쉬운점

• O(N)
  • 갈 수 없는 부분을 움직이면서 체크하기 = 맵크기 * 체크 크기 = (N*M)*(H*W) = 1000^4 = 시간초과
  • 체크 크기를 모서리 4개만 체크해도 됨 = (N*M)*4
  • 갈 수 없는 부분 체크 후 맵 탐색 = 맵 크기 = N*M = 1000^2
• 벽 검사할때 왼쪽위 기준으로 못가는 경계임. 왼쪽위를 고정으로 무조건 오른쪽 아래로뻗침. 못가는 범위는 H*W임
  • 2H*2W가 아니라
• 인덱스 실수
  • 못가는 경로 마킹 체크 인덱스 H,W로 함
  • N,M으로 해야함
• 꼼꼼함
  • 벽 기준으로 못가는 부분 체크
  • 경계부분에서 못가는 부분 체크 안했음
    • if(nr>=0 && nr<N && nc>=0 && nc<M && visited[nr][nc]==0) {
    • if(nr>=0 && nr<N-H+1 && nc>=0 && nc<M-W+1 && visited[nr][nc]==0) {

잘한점

• visited배열 만들고 바로 이용해서 BFS 돌렸음
  • 실행시간 빠르게 나온 듯
• O(N)에서 막혔지만 역으로 갈 수 없는 부분 체크 미리 해놓는다는 생각 함