백준 2178번 ) 미로 탐색 (java)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

문제

풀이

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

public class Main {

    static int[][] map;
    static int N, M;
    static boolean[][] visited;
    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());

        map = new int[N][M];
        for(int i=0; i<N; i++){
            String line = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = line.charAt(j) - '0';
            }
        }

        visited = new boolean[N][M];
        visited[0][0] = true;
        bfs(0, 0);
        System.out.println(map[N-1][M-1]);
    }

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

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while(!q.isEmpty()){
            int now[] = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i=0; i<4; i++){
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
                if(visited[nextX][nextY] || map[nextX][nextY] == 0) continue;

                q.add(new int[] {nextX, nextY});
                map[nextX][nextY] = map[nowX][nowY] + 1;
                visited[nextX][nextY] = true;
            }
        }
    }
}

dfs로 푸는 문제인줄 알았는데, 시간초과가 나서 BFS로 풀어야하는 문제라고 한다.

현재 좌표의 위아래양옆을 모두 살펴보고, 1인 경우 현재의 위치에서 최단 경로 + 1 해서 저장하고, 큐에 넣으면서 꺼내 비교하는 방식으로 진행한다.

방문한 좌표는 따로 배열에 방문 여부를 저장하여 체크한다.

 

 

알아둘 점!

• BFS 는 Queue를 사용하여 구현한다.
  • Queue 구현 방법에, 이번에는 좌표 배열을 넣어야 하므로, Queue<int[]> q = new LinkedList<>(); 와 같이 구현하였다.
  • 좌표는 배열로 x, y 앞뒤로 지정하여 반복문으로 체크한다.

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

• BFS를 사용하여 풀이해야하는 경우!!!
  • 최소 비용 문제 (또는 최단경로)
  • 간선의 가중치가 1인 경우
  • 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내 만족)