2178 미로 탐색

BOJ::2178 미로 탐색

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

bfs를 이용해 미로의 최단경로를 구하는 문제.

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n,m,x,y,ax,ay;
    static int map[][]=new int[101][101];
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    
    public static void main(String args[]) throws NumberFormatException, 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());
        
        for(int i = 1 ; i<= n; i++){
            String s = br.readLine();
            for(int j = 1 ; j <= m ; j++){
                map[i][j]=s.charAt(j-1)-'0';
            }
        }
        
        bfs(1,1);
        System.out.println(map[n][m]);
    }
    
    public static void bfs(int a,int b){
        Queue<Node> q = new LinkedList();
        q.add(new Node(a,b));
        while(!q.isEmpty()){
            x = q.peek().x;
            y = q.poll().y;
            for(int i = 0 ; i < 4 ; i++){
                ax = x+dx[i];
                ay = y+dy[i];
                if(ax>0&&ay>0&&ax<=n&&ay<=m){
                    if(map[ax][ay]!=0){
                        if(map[ax][ay]==1 || map[ax][ay]>map[x][y]+1){
                            map[ax][ay]=map[x][y]+1;
                            q.add(new Node(ax,ay));
                        }
                    }
                }
            }
        }
    }
}
class Node{
    int x;
    int y;
    Node(int _x, int _y){
        x=_x;
        y=_y;
    }
}

<C++>

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
int n, m, x, y, ax, ay;
int map[101][101];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
class Node {
public:
    int x;
    int y;
    Node(int _x, int _y) {
        x = _x;
        y = _y;
    }
};
 
void bfs(int a, int b) {
    queue<Node> q;
    q.push(Node(a, b));
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            ax = x + dx[i];
            ay = y + dy[i];
            if (ax > 0 && ay > 0 && ax <= n && ay <= m) {
                if (map[ax][ay] != 0) {
                    if (map[ax][ay] == 1 || map[ax][ay] > map[x][y] + 1) {
                        map[ax][ay] = map[x][y] + 1;
                        q.push(Node(ax, ay));
                    }
                }
            }
        }
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            map[i][j] = s.at(j - 1) - '0';
        }
    }
 
    bfs(1, 1);
    cout << map[n][m] << endl;
}