[BaekJoon][1261] 알고스팟

BAEKJOON ONLINE JUDGE

1261 알고스팟

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

입력이 0일 경우에는 벽을 부술 필요 없이 바로 이동하면 되므로 DFS이건 BFS이건 탐색을 하면 된다.

입력이 1일 경우에는 벽을 부수어야 하기 때문에 바로 이동을 하면 안된다.

단계별로 나누면

1. 바로 갈 수 있는 곳은 바로간다.

2. 더이상 갈 수 없으면 벽을 부순다.

3. 벽을 부순 후 갈 수 있는만큼 이동한다.

이걸 반복해서 마지막 장소에 도착하면 된다.

풀이 1. 

입력이 0인 곳은 DFS, 그 중 벽을 만나면 queue에 저장

DFS가 끝난 후 queue에 저장된 벽을 부순 후 다시 DFS를 타서 바로 갈 수 있는 곳은 이동

이동하면서 다시 벽을 만나면 queue에 저장

#include <stdio.h>
#include <queue>
using namespace std;
 
typedef struct tagData {
    int y;
    int x;
    int cnt;
}Data;
 
int map[101][101];
int inputdata[101][101];
queue<Data> que;
int n, m;
 
void init()
{
    int i, j;
 
    for (i = 0; i < 101; i++) {
        for (j = 0; j < 101; j++) {
            map[i][j] = -1;
        }
    }
}
 
void input()
{
    int i, j;
 
    scanf("%d %d", &m, &n);
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%1d", &inputdata[i][j]);
        }
    }
}
 
void print()
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (map[i][j] < 0)    printf(" ");
            else printf("%d", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
 
Data makedata(int y, int x, int cnt)
{
    Data data;
    data.y = y;
    data.x = x;
    data.cnt = cnt;
    return data;
}
 
void dfs(int y, int x, int cnt) 
{
    int dx[4] = { -1, 0, 0, 1 };
    int dy[4] = { 0, -1, 1, 0 };
    int nexty, nextx;
    int i;
 
    map[y][x] = cnt;
 
    for (i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < n && nextx >= 0 && nextx < m) {
            if(map[nexty][nextx] < 0 && !inputdata[nexty][nextx])        
                dfs(nexty, nextx, cnt);
            else {
                map[nexty][nextx] = cnt + 1;
                que.push(makedata(nexty, nextx, cnt + 1));
            }
        }
    }
}
 
void go()
{
    Data data;
    int dx[4] = { -1, 0, 0, 1 };
    int dy[4] = { 0, -1, 1, 0 };
    int tempy, tempx;
    int flag;
    int i;
 
    dfs(0, 0, 0);
 
    while (map[n - 1][m - 1] < 0 && !que.empty()) {
        data = que.front();
        que.pop();
 
        flag = 1;
        for (i = 0; i < 4; i++) {
            tempy = data.y + dy[i];
            tempx = data.x + dx[i];
            if (tempy >= 0 && tempy < n && tempx >= 0 && tempx < m) {
                if (map[tempy][tempx] < 0 && !inputdata[tempy][tempx]) {
                    flag = 0;
                    dfs(tempy, tempx, data.cnt);
                }
            }
        }
 
        if (flag) {
            for (i = 0; i < 4; i++) {
                tempy = data.y + dy[i];
                tempx = data.x + dx[i];
                if (tempy >= 0 && tempy < n && tempx >= 0 && tempx < m) {
                    if (map[tempy][tempx] < 0 && inputdata[tempy][tempx]) {
                        que.push(makedata(tempy, tempx, data.cnt + 1));
                    }
                }
            }
        }
    }
}
 
int main()
{
    init();
 
    input();
 
    go();
 
    printf("%d\n", map[n - 1][m - 1]);
 
    return 0;
}

풀이 2. 

입력이 0인 지점은 바로 이동

벽을 만나면 +1을 한 후 더이상 이동하지 않는다.
이동할 수 있는곳을 다 탐색한 후

다시 map을 돌면서 마지막으로 벽을 부수었던 곳을 찾아 다시 DFS

#include <stdio.h>
 
int n, m;
int map[100][100];
int count[100][100];
 
void input()
{
    int i, j;
 
    scanf("%d %d", &m, &n);
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
}
 
void print()
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            printf("%d ", count[i][j]);
        }
        printf("\n");
    }
}
 
void dfs(int y, int x, int cnt)
{
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    int i;
    int nexty, nextx;
 
    if (!count[y][x]) {
        if (map[y][x]) {
            count[y][x] = cnt + 1;
            return;
        }
        count[y][x] = cnt;
    }
 
    for (i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty < n && nexty >= 0 && nextx < m && nextx >= 0 && !count[nexty][nextx]) {
            dfs(nexty, nextx, cnt);
        }
    }
}
 
void process()
{
    int cnt;
    int i, j;
 
    count[0][0] = cnt = 1;
 
    while (count[n - 1][m - 1] == 0) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (count[i][j] == cnt) {
                    dfs(i, j, cnt);
                    if (count[n - 1][m - 1])    return;
                }
            }
        }
        cnt++;
    }
}
 
int main()
{
    input();
 
    process();
 
    printf("%d\n", count[n - 1][m - 1] - 1);
 
    return 0;
}

* queue를 사용한 것보다 그냥 배열을 처음부터 탐색해가는 것이 더 속도가 빨랐다.

ex) 풀이 1 : 8ms, 풀이 2 : 9ms