[코드트리] n x m 표 이동 7 (BFS_Grid이용)- JAVA

알고리즘 스터디 - BFS

https://www.codetree.ai/training-field/search/problems/move-n-x-m-table-7/description?page=1&pageSize=20&tags=BFS&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

# 문제

 

# 예제

입력

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

 

출력

7

 

# 필요개념

 

BFS문제 중에서는 grid형태를 띄는 문제들이 있다. 이 경우에는 dx, dy 테크닉을 사용한다. 

 

 

dy dx 테크닉

주어진 위치에서 상하좌우를 탐색할 때 사용한다. if문으로 모두 쓰면 코드가 길어져서, 위치마다 x와 y의 변화량을 각각의 배열에 담는다. 이때 순서를 잘 맞추어야 하는데, 어떤 점을 기준으로 위에 있는 좌표는 y좌표만 -1하면 되기 때문에, dy는 -1, dx는 0을 담는다.

 

 

풀이 흐름

문제풀이 흐름은 다음과 같이 생각했다.

 

1. 1의 값이 주어진 곳은 벽이라고 생각하고, 방문했다고 가정한다.
2. 직사각형의 왼쪽 위를 기준점으로 잡는다. 그러고 오른쪽 아래점을 담아둔다. (각각 h와 w를 더하고 1 뺀 값)
3. 이동 방향에 따라 가능여부 검사를 달리한다. 이렇게 하면 직사각형을 모두 검사하는 것보다 시간을 단축할 수 있다.

 

4. 목적지에 도달하면 count를 리턴한다.

 

 

# Code

import java.util.*;
import java.io.*;

public class Main {

    static int rNum;
    static int cNum;
    static int[][] maze;
    static boolean[][] isVisit;

    static int[] initLeftTop;
    static int[] goal;

    static int[] dx = {0, 1, 0, -1}; // 북 동 남 서
    static int[] dy = {-1, 0, 1, 0};

    static int h;
    static int w;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rNum = Integer.parseInt(st.nextToken());
        cNum = Integer.parseInt(st.nextToken());
        maze = new int[rNum][cNum];
        isVisit = new boolean[rNum][cNum];

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

        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        initLeftTop = new int[] {Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1};
        goal = new int[] {Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1};

        int result = bfs();
        System.out.print(result);
    }

    public static int bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{initLeftTop[0], initLeftTop[1], 0}); // {y, x, count}
        isVisit[initLeftTop[0]][initLeftTop[1]] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cy = current[0];
            int cx = current[1];
            int count = current[2];

            if (cy == goal[0] && cx == goal[1]) {
                return count;
            }

            for (int i = 0; i < 4; i++) { // 북 동 남 서
                int ny = cy + dy[i];
                int nx = cx + dx[i];

                if (canMove(ny, nx, i)) {
                    isVisit[ny][nx] = true;
                    queue.add(new int[]{ny, nx, count + 1});
                }
            }
        }

        return -1; // 이동할 수 없는 경우
    }

    public static boolean canMove(int y, int x, int idx) {
        if (y < 0 || y + h > rNum || x < 0 || x + w > cNum) {
            return false;
        }
        if (isVisit[y][x]) {
            return false;
        }


        if (idx == 0) { // 북
            for (int i = x ; i < x + w ; i++) {
                if (maze[y][i] == 1) return false;
            }
        } 
        else if (idx == 1) { // 서
            for (int i = y ; i < y + h ; i++) {
                if (maze[i][x + w - 1] == 1) return false;
            }
        } 
        else if (idx == 2) { // 남
            for (int i = x ; i < x + w ; i++) {
                if (maze[y + h - 1][i] == 1) return false;
            }    
        } 
        else if (idx == 3) {   // 동 
            for (int i = y ; i < y + h ; i++) {
                if (maze[i][x] == 1) return false;
            }
        }

        return true;
    }
}

 

# 결과