[백준] bfs - 2178번 미로탐색 (Java)

 

문제링크

2178번: 미로 탐색

 

접근한 방법

• 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다.

 

---

풀이방법

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.
시작지점(0,0)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

---

소스코드 작성 방법

• 미로의 크기(n, m)을 전역 필드로 선언한다.
• 미로의 정보(maze), 방문 여부 및 거리(visited)도 전역 필드로 선언한다.
• 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
• 행과 열의 index를 저장할 수 있는 클래스를 선언한다.
  
  
• bfs 메소드를 선언하여 아래와 같이 처리해준다.
• 큐를 초기화 시켜준다.
• 큐에 맨 처음 좌표의 객체를 넣어준다.
• 처음 칸도 지나는 것에 포함되므로 visited[0][0] = 1 로 처리해주어, 방문 처리 및 거리를 저장한다.
• while문으로 큐에 남아있는 게 없을 때까지 탐색을 수행한다.
  • q.poll()로 큐에서 좌표 객체를 꺼내 현재 좌표인 curR, curC 필드에 저장한다.
  • 반복문으로 현재 좌표에서 4방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 미로의 크기를 벗어나거나 미로의 값이 0이여서 진행하지 못할 시 continue로 넘어간다.
  • 미로의 값이 1이고 아직 방문하지 않았다면(visited의 좌표가 0이라면) visited[nextR][nextC]에 visited[curR][curC] + 1을 저장한다. (현재까지의 칸 수 + 1)
  • 큐에 다음 좌표의 객체를 넣어준다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q_2178_Maze_20210723 {
    public static int n,m;
    public static int[][] maze;
    public static int[][] visited;
    public static int[] dx = {-1,0,1,0};
    public static int[] dy = {0,-1,0,1};


    public static void bfs(){
        Queue<Pair> q = new LinkedList();
        q.add(new Pair(0, 0));
        visited[0][0] = 1; // 처음 칸도 지나는 것에 포함되므로 1로 처리

        while(!q.isEmpty()){
            Pair cur = q.poll();
            int curR = cur.r;
            int curC = cur.c;

            for(int i=0 ; i<4 ; i++){
                int nextR = curR + dx[i];
                int nextC = curC + dy[i];

                if(nextR < 0 || nextC < 0 || nextR >=n || nextC >=m) continue;
                if(maze[nextR][nextC] == 0) continue;
                if(maze[nextR][nextC] == 1 && visited[nextR][nextC] == 0) {
                    visited[nextR][nextC] = visited[curR][curC] + 1;
                    q.add(new Pair(nextR,nextC));
                }
            }

        }

    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        maze = new int[n][m];
        visited = new int[n][m];

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

        bfs();
        bw.write(visited[n-1][m-1]+"");

        br.close();
        bw.close();
    }

    public static class Pair{
        int r;
        int c;

        public Pair(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}