BOJ 2178 (미로 탐색)

초기 아이디어

최단 거리를 묻는 문제는 우선 직관적으로 DFS, BFS 를 생각할 수 있다. 더 코드가 짧은 DFS 를 하기로 해보고 연습겸 BFS 로도 구현해보기로 한다.

문제 풀이

1. DFS

#include<bits/stdc++.h>
using namespace std;

int a[101][101];
int visited[101][101];
int n, m, ret=987654321;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(int x, int y, int dept){
    if(x==n-1 && y==m-1) {
        ret = ret>dept?dept:ret;
        return;
    }
    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx<0||nx>n||ny<0||ny>m) continue;
        if(a[nx][ny]==0 || visited[nx][ny]) continue;
        visited[nx][ny] = 1;
        dfs(nx, ny, dept + 1);
        visited[nx][ny] = 0;
    }
    return;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%1d", &a[i][j]);
        }
    }
    dfs(0, 0, 1);
    cout << ret;
}

시간초과가 뜨길래 그제서야 생각해보니 모든 칸이 1로 채워진 경우에는 너무 많은 경우의 수가 나온다. 확실히 DFS, BFS 의 기로에 놓인 상황이면 고민을 해봐야한다.

2. BFS

#include<bits/stdc++.h>
using namespace std;

int a[101][101];
int visited[101][101];
int n, m, ret=987654321;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%1d", &a[i][j]);
        }
    }

    queue<pair<int, int>> q;
    visited[0][0] = 1;
    q.emplace(0, 0);
    while(!q.empty()){
        pair<int, int> now = q.front(); q.pop();
        if(now.first == n-1 &&  now.second == m-1) break;
        for(int i=0;i<4;i++){
            int nx = now.first + dx[i];
            int ny = now.second + dy[i];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(a[nx][ny]==0 || visited[nx][ny]!=0) continue;   
            q.emplace(nx, ny);
            visited[nx][ny] = visited[now.first][now.second] + 1;
        }
    }

    cout << visited[n-1][m-1];
}

통과 됨

---

DFS, BFS 는 가장 기본이라 오랜만에 풀어도 시간이 조금 더 걸리긴 했지만 무난하게 풀 수 있었다