[코드트리] n x m 표 이동 5 (BFS) - JAVA

알고리즘 스터디 - BFS

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

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

 

 

# 문제

 

# 예제

입력

4 6
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

 

출력 :  (1, 1)에서 (n, m)까지 최소한의 횟수로 이동할 때 그 횟수를 출력합니다.

15

 

# 필요개념

 

첫 위치에서 4개의 방향을 모두 보고, 움직여야 하기 때문에 BFS를 이용해 풀었다.

 

BFS

BFS는 너비 우선 탐색 알고리즘을 뜻하며, 구현할 때에는 큐 자료구조를 이용한다.

이 문제에서는 값을 이용하는 게 아니라, x와 y 인덱스를 이용해야 하므로 큐에 int형 배열을 넣어주었다.

 

현 위치에서 동서남북을 탐색해야 하므로 dx와 dy 배열을 만들어 코드의 수를 줄였다 !

 

문제에서의 조건은, 도착점으로 가는 가장 적은 움직임 수를 출력해야하기 때문에, 거리를 담아줄 이차원배열을 따로 생성하여 이동할 때마다 기존의 +1을 해주었다. while문의 종료조건으로는 도착지점에 도달했을 때를 if문으로 넣어주었다.

 

 

# Code

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

public class Main {

    static int[][] maze;
    static boolean[][] isVisit;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {0, 1, 0, -1}; // 동 남 서 북
    static int[] dy = {1, 0, -1, 0};

    static int rNum;
    static int cNum;

    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());
            }
        }
        System.out.println(bfs(0, 0));
    }

    public static int bfs(int y, int x) {
        queue.add(new int[]{y, x});
        isVisit[y][x] = true;
        int[][] distance = new int[rNum][cNum];
        distance[y][x] = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int presentY = current[0];
            int presentX = current[1];

            // 도착지점에 도달하면 그 지점까지의 거리 반환
            if (presentX == cNum - 1 && presentY == rNum - 1) {
                return distance[presentY][presentX];
            }

            for (int i = 0 ; i < 4 ; i++) {
                int yIdx = presentY + dy[i];
                int xIdx = presentX + dx[i];
                if (isValid(yIdx, xIdx) && maze[yIdx][xIdx] == 1 && !isVisit[yIdx][xIdx]) {
                    queue.add(new int[]{yIdx, xIdx});
                    isVisit[yIdx][xIdx] = true;
                    distance[yIdx][xIdx] = distance[presentY][presentX] + 1;
                }
            }
        }
        return 0;
    }

    public static boolean isValid(int y, int x) {
        return y >= 0 && y < rNum && x >= 0 && x < cNum;
    }
}

 

# 결과