(9) [C++, Java] 백준 No.2178 : 미로탐색

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/400?category=864321

 

# C++

#include<cstdio>
#include<queue>
using namespace std;

int miro[101][101]; // 0 : 이동할 수 없는 칸, 1 : 이동할 수 있는 칸
int dist[101][101]; // check배열의 역할 및 0 : 방문 안한 것, 1이상 : 방문한 것이면서 1,1로부터의 거리
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int h, w;

int main()
{
    scanf("%d %d", &h, &w);

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            miro[i][j] = 0;
            dist[i][j] = 0;
        }
    }

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            scanf("%1d", &miro[i][j]);
        }
    }

    //BFS탐색을 진행하면서 거리를 구해준다.
    queue<pair<int, int>> q;

    q.push(make_pair(1, 1)); // 1, 1부터 탐색 시작
    dist[1][1] = 1;

    while(!q.empty()){
        pair<int, int> p = q.front();
        q.pop();
        int cx = p.first;
        int cy = p.second;

        for(int k = 0; k < 4; k++){
            int nx = cx + dx[k];
            int ny = cy + dy[k];

            if(nx >= 1 && nx <= h && ny >= 1 && ny <= w){
                if(dist[nx][ny] == 0 && miro[nx][ny] == 1){
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[cx][cy] + 1;
                }
            }
        }
    }

    printf("%d\n", dist[h][w]);
}

# Java

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        sc.nextLine();
        for (int i=0; i<n; i++) {
            String s = sc.nextLine();
            for (int j=0; j<m; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        int[][] dist = new int[n][m];
        boolean[][] check = new boolean[n][m];
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(0, 0));
        check[0][0] = true;
        dist[0][0] = 1;
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (check[nx][ny] == false && a[nx][ny] == 1) {
                        q.add(new Pair(nx, ny));
                        dist[nx][ny] = dist[x][y] + 1;
                        check[nx][ny] = true;
                    }
                }
            }
        }
        System.out.println(dist[n-1][m-1]);
    }
}