[BOJ][2178] 미로 탐색

1. 문제 링크

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

2. 사용 알고리즘

BFS

3. 풀이

단계별로 진행한다는 BFS의 성질을 이용

1) 이동가능 여부를 저장하는 arr 배열, 이동 거리 및 방문여부를 저장하기 위한 check 배열 선언

2) (1, 1)부터 BFS 탐색 시작

• 현재 정점의 y, x - 1 좌표가 유효하고, 이동 가능(arr[y][x - 1] == 1)하고, 아직 방문하지 않은 경우(check[y][x - 1] == 0)

  • check[y][x - 1] = check[y][x] + 1

• 현재 정점의 y - 1, x 좌표가 유효하고, 이동 가능(arr[y - 1][x] == 1)하고, 아직 방문하지 않은 경우(check[y - 1][x] == 0)

  • check[y - 1][x] = check[y][x] + 1

• 현재 정점의 y, x + 1 좌표가 유효하고, 이동 가능(arr[y][x + 1] == 1)하고, 아직 방문하지 않은 경우(check[y][x + 1] == 0)

  • check[y][x + 1] = check[y][x] + 1

• 현재 정점의 y + 1, x 좌표가 유효하고, 이동 가능(arr[y + 1][x] == 1)하고, 아직 방문하지 않은 경우(check[y + 1][x] == 0)

  • check[y + 1][x] = check[y][x] + 1

3) 2)의 과정을 반복하며 BFS 탐색 완료

4) check[n][m] 출력

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/2178.cpp

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;
int arr[103][103];
int check[103][103];
queue<pair<int, int>> q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int a, int b) {
    check[a][b] = 1;
    q.push(make_pair(a, b));
    while(!q.empty()) {
        pair<int, int> temp = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = temp.first + dy[i], nx = temp.second + dx[i];
            if(ny >= 1 && ny <= n && nx >= 1 && nx <= m && arr[ny][nx] && !check[ny][nx]) {
                check[ny][nx] = check[temp.first][temp.second] + 1;
                q.push(make_pair(ny, nx));
            }
        }
    }
}

int main(void) {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for(int j = 1; j <= m; ++j) arr[i][j] = s[j - 1] - 48;
    }
    bfs(1, 1);
    cout << check[n][m] << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/2178.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;

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

public class Main {
    
    static int n, m;
    static int arr[][] = new int[103][103];
    static int check[][] = new int[103][103];
    static Queue<Pair> q = new LinkedList<Pair>();
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};

    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());
        for(int i = 1; i <= n; ++i) {
            String s = br.readLine();
            for(int j = 1; j <= m; ++j) arr[i][j] = s.charAt(j - 1) - 48;
        }
        bfs(1, 1);
        System.out.println(check[n][m]);
    }

    public static void bfs(int a, int b) {
        check[a][b] = 1;
        q.add(new Pair(a, b));
        while(!q.isEmpty()) {
            Pair temp = q.poll();
            for(int i = 0; i < 4; ++i) {
                int ny = temp.y + dy[i], nx = temp.x + dx[i];
                if(ny >= 1 && ny <= n && nx >= 1 && nx <= m && arr[ny][nx] == 1 && check[ny][nx] == 0) {
                    check[ny][nx] = check[temp.y][temp.x] + 1;
                    q.add(new Pair(ny, nx));
                }
            }
        }
    }
}