[Java] BFS의 활용 - 최단거리

문제

[백준 1260번]
N×M크기의 배열로 표현되는 미로가 있다.

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은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 
붙어서
 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

예시

 

풀이

BFS를 이용하여 미로의 최단거리를 구하는 문제이다.

 

0. 성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static Set<int[]> visited = new HashSet<>(); //방문한 리스트

    public static int[][] map;

    public static int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; //방향배열 - 상, 하, 좌, 우

    public static int n;
    public static int m;

    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());

        // n*m 크기의 배열 (미로)
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = temp.charAt(j) - '0' ;
            }
        }


        bfs(0, 0); // (0, 0)부터 시작
        System.out.println(map[n-1][m-1]);
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();

        int[] first = {x, y};

        queue.offer(first); // Queue에 현재 노드 넣기
        visited.add(first); // 방문 기록

        while (!queue.isEmpty()) { // Queue가 빌 때까지 반복
            int[] current = queue.poll(); // Queue에서 현재 값 꺼내기

            //인접한 노드들 모두 방문 - 상, 하, 좌, 우 모두 방문
            for (int i = 0; i<4; i++) {

                int[] next = {current[0] + direction[i][0], current[1] + direction[i][1]};

                if(next[0] >= 0 && next[1] >= 0 && next[0] < n && next[1] < m) { //map bound에 넘치는지 검사
                    if( map[next[0]][next[1]] == 1 && !visited.contains(next)) { //갈 수 있는 길인지 & 방문 했던 길인지 검사
                        queue.add(next);
                        map[next[0]][next[1]] = map[current[0]][current[1]] + 1;
                        visited.add(next);
                    }
                }
            }
        }
    }

}

 

1. 문제 풀이

input

public static Set<int[]> visited = new HashSet<>(); //방문한 리스트

public static int[][] map;

public static int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; //방향배열 - 상, 하, 좌, 우

public static int n;
public static int m;
    
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

// n*m 크기의 배열 (미로)
map = new int[n][m];

for (int i = 0; i < n; i++) {
    String temp = br.readLine();
    for (int j = 0; j < m; j++) {
        map[i][j] = temp.charAt(j) - '0' ;
    }
}

 

미로를 입력받아 2차원 배열에 넣어두었다.

 

미로 내에 방향을 찾아가기 위해 방향배열 상, 하, 좌, 우를 선언해 두었다.

 

 

 

BFS

public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();

        int[] first = {x, y};

        queue.offer(first); // Queue에 현재 노드 넣기
        visited.add(first); // 방문 기록

        while (!queue.isEmpty()) { // Queue가 빌 때까지 반복
            int[] current = queue.poll(); // Queue에서 현재 값 꺼내기

            //인접한 노드들 모두 방문 - 상, 하, 좌, 우 모두 방문
            for (int i = 0; i<4; i++) {

                int[] next = {current[0] + direction[i][0], current[1] + direction[i][1]};

                if(next[0] >= 0 && next[1] >= 0 && next[0] < n && next[1] < m) { //map bound에 넘치는지 검사
                    if( map[next[0]][next[1]] == 1 && !visited.contains(next)) { //갈 수 있는 길인지 & 방문 했던 길인지 검사
                        queue.add(next);
                        map[next[0]][next[1]] = map[current[0]][current[1]] + 1;
                        visited.add(next);
                    }
                }
            }
        }
    }

 

Queue를 이용하여 BFS를 구현하였다.

 

이전 BFS 기본 문제와 다르게, 좌표 (x, y)를 이용하기 위해 배열을 이용해서 표현했다.

 

1. 처음 시작 노드를 Queue에 넣어둔다.

2. while문을 시작한다.

  2-1. Queue에서 현재 노드를 꺼낸다.

  2-2. 상, 하, 좌, 우를 모두 방문하는 for문을 시작한다.

    2-2-1. 방향배열을 통해 다음 좌표를 저장해둔다.

    2-2-2. map bound를 넘치는지 검사한다.

    2-2-3. 갈 수 있는 좌표인지 검사한다.

    2-2-4. 이미 방문한 좌표인지 검사한다.

    2-2-5. Queue에 다음 좌표를 넣어둔다.

    2-2-6. Queue에 현재 좌표 + 1 값을 다음 좌표에 넣어둔다.

    2-2-7. 다음 좌표를 방문 기록 해둔다.