[BOJ-2178]미로찾기

11달전에 풀었었는데 

그때 코드를 보고

물론 지금도 못짜지만, 그때는 더 못짰구나를 볼 수 있었다. 

1,1 부터 N,M 까지의 최단 거리(최단 칸수) 를 구하면 되는 것이었다.

#include <stdio.h>
#include <queue>
using namespace std;
 
int main() {
    bool mat[102][102] = { 0 }, visit[102][102] = { 0 };
    pair<char, char> p(1, 1), t;
    int n, m, i, j;
    char prev[101] = "";
    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= n; i++) {
        gets(prev);
        for (j = 1; j <= m; j++) mat[i][j] = prev[j - 1] - '0';
    }
    queue< pair<char, char> > que;
    int cnt = 1, tmp, popcnt = 1;
    que.push(p);
    while (1) {
        for (tmp = i = 0; i < popcnt; i++) {
            p = que.front();
            if (p.first == n && p.second == m) {
                printf("%d", cnt);
                return 0;
            }
            que.pop();
            if (mat[p.first - 1][p.second] && !visit[p.first - 1][p.second]) {
                tmp++;
                t.first = p.first - 1;
                t.second = p.second;
                que.push(t);
                visit[p.first - 1][p.second] = 1;
            }
            if (mat[p.first + 1][p.second] && !visit[p.first + 1][p.second]) {
                tmp++;
                t.first = p.first + 1;
                t.second = p.second;
                que.push(t);
                visit[p.first + 1][p.second] = 1;
            }
            if (mat[p.first][p.second - 1] && !visit[p.first][p.second - 1]) {
                tmp++;
                t.first = p.first;
                t.second = p.second - 1;
                que.push(t);
                visit[p.first][p.second - 1] = 1;
            }
            if (mat[p.first][p.second + 1] && !visit[p.first][p.second + 1]) {
                tmp++;
                t.first = p.first;
                t.second = p.second + 1;
                que.push(t);
                visit[p.first][p.second + 1] = 1;
            }
        }
        popcnt = tmp;
        cnt++;
    }
}
 

#include<cstdio>
#include<vector>
#include<queue>
struct info{
    int r;
    int c;
    int m;
    info(int ir, int ic, int im):r(ir), c(ic), m(im) {}
};
using namespace std;
typedef vector<int> VI;
VI imap[111];
int dr[] = {-1,0,1,0};
int dc[] = {0,-1,0,1};
int main(){
    int row, col; scanf("%d%d", &row, &col);
    for(int r = 0 ; r < row ; r++){
        imap[r].resize(col);
        char temp[111] = {0,};
        scanf("%s", &temp);
        for(int c = 0 ; c < col ; c++){
            imap[r][c] = temp[c] - '0';
        }
    } // input
    
    queue<info> Q;
    Q.push(info(0,0,1));
    imap[0][0] = 0;
    while(!Q.empty()){
        info here = Q.front(); Q.pop();
        
        int here_row = here.r;
        int here_col = here.c;
        int here_mov = here.m;
 
        if(here_row == row-1 && here_col == col-1){
            printf("%d",here_mov);
            return 0;
        }
        for(int i = 0 ; i < 4 ; i++){
            int there_row = here_row + dr[i];
            int there_col = here_col + dc[i];
            if(0 <= there_row && there_row < row &&
                0 <= there_col && there_col < col){
                if(imap[there_row][there_col] == 1){
                    Q.push(info(there_row, there_col, here_mov + 1));
                    imap[there_row][there_col] = 0;
                }
            }
        }
    }
    
    return 0;
}
 

DFS로 작성하니 시간초과를 받았다.

#include<cstdio>
#include<vector>
#include<queue>
 
using namespace std;
typedef vector<int> VI;
VI imap[111];
int dr[] = {-1,0,1,0};
int dc[] = {0,-1,0,1};
int row, col; 
int min2(int a, int b){
    return a>b?b:a;
}
int dfs(int r, int c, int m){
    int ret = 9999;
    if(r == row-1 && c == col-1) return m;
 
    for(int i = 0 ; i < 4 ; i++){
        int tr = r+dr[i];
        int tc = c+dc[i];
        if(0 <= tr && tr < row &&
            0 <= tc && tc < col){
                if(imap[tr][tc] == 1){
                    imap[tr][tc] = 0;
                    ret = min2(ret,dfs(tr,tc,m+1));
                    imap[tr][tc] = 1;
                }
        }
    }
    return ret;
}
 
int main(){
    scanf("%d%d", &row, &col);
    for(int r = 0 ; r < row ; r++){
        imap[r].resize(col);
        char temp[111] = {0,};
        scanf("%s", &temp);
        for(int c = 0 ; c < col ; c++){
            imap[r][c] = temp[c] - '0';
        }
    } // input
    
    printf("%d", dfs(0,0,1));
    
    return 0;
}