[BOJ] 백준 2665 미로만들기

출처: https://www.acmicpc.net/problem/2665

Approach

BFS 혹은 DFS 이용해서 해결할 수 있다.

BFS (Breadth-First Search, 너비 우선 탐색) 

BFS (Breadth-First Search, 너비 우선 탐색)

 

DFS (depth-first search, 깊이 우선 탐색) 

깊이 우선 탐색(depth-first search, DFS)

 

DFS와 BFS 비교 

DFS와 BFS 비교

 

DFS

#include <stdio.h>
const int MAX_N = 50 + 2;
int N, A[MAX_N][MAX_N], L[MAX_N][MAX_N];
int dx[] = { 0, 0, 1, -1 }, dy[] = { 1, -1, 0, 0 };
char str[MAX_N];

void input() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%s", str + 1);
        for (int j = 1; j <= N; ++j) {
            A[i][j] = 1 - (str[j] - '0');
            L[i][j] = 99;
        }
    }
}
void DFS(int x, int y, int lev) {
    if (x < 1 || x > N || y < 1 || y > N)
        return;

    if (L[x][y] <= lev + A[x][y])
        return;

    L[x][y] = lev + A[x][y];

    for (int i = 0; i < 4; ++i) {
        DFS(x + dx[i], y + dy[i], L[x][y]);
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    DFS(1, 1, 0);
    printf("%d\n", L[N][N]);
}

 

BFS

#include <stdio.h>
const int MAX_N = 55;
const int INF = 100;
int N, A[MAX_N][MAX_N], L[MAX_N][MAX_N];
struct Data {
    int x, y, lev;
}que[MAX_N * MAX_N * INF];
int fr, re;


void input(){
    scanf("%d", &N);
    for (int x = 1; x <= N; ++x) {
        for (int y = 1; y <= N; ++y) {
            scanf("%1d", A[x] + y);
            A[x][y] = !A[x][y];
            L[x][y] = INF;
        }
    }
}

void push(int nextX, int nextY, int nl) {
    if (L[nextX][nextY] <= nl + A[nextX][nextY]) return;
    L[nextX][nextY] = nl + A[nextX][nextY];
    que[re++] = { nextX, nextY, L[nextX][nextY] };
}

int BFS() {
    Data cur;
    push(1, 1, 0);

    while (fr < re) {
        cur = que[fr++];
        for (int i = 0; i < 4; ++i) {
            push(cur.x + "0211"[i] - '1', cur.y + "1102"[i] - '1', cur.lev);
        }
    }

    return L[N][N];
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", BFS());
}