M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1261 - 알고스팟

최대 1 분 소요

문제

백준 1261 - 알고스팟 풀러가기

문제 분석

이 문제의 경우에는 벽을 뚫는 경우에는 1 벽을 뚫지 않아도 되는 경우에는 0 의 가중치로 이루어진 그래프라고 생각 할 수 있다.

bfs는 모든 가중치가 1인 경우에 적용할 수 있다고 생각하여 bfs로 풀 수 없다고 생각 할 수 있는데, 그렇지 않다.

큐를 2개 이용하거나, 덱을 이용하면 bfs로 풀 수 있다.

문제 풀이(C++)

  1. 덱을 이용한 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    #include <cstdio>
    #include <deque>
     
    using namespace std;
     
    int main() {
     
        int maze[101][101];
     
        int visit[101][101];
     
        int dx[] = { 0, 0,1,-1 };
        int dy[] = { 1, -1,0,0 };
     
        deque<pair<int, int>> d;
     
        int m, n;
     
        scanf("%d %d", &m, &n);
     
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%1d", &maze[i][j]);
                visit[i][j] = -1;
            }
        }
     
        d.push_back(make_pair(1, 1));
        visit[1][1] = 0;
     
        while (!d.empty()) {
            int cy = d.front().first;
            int cx = d.front().second;
     
            d.pop_front();
     
            for (int i = 0;i < 4; i++) {
                int ny = cy + dy[i];
                int nx = cx + dx[i];
     
                if (nx >= 1 && nx <= m && ny >= 1 && ny <= n) {
                    if (visit[ny][nx] == -1) {
                        if (maze[ny][nx]==0) {
                            d.push_front(make_pair(ny, nx));
                            visit[ny][nx] = visit[cy][cx];
                        }
                        else {
                            d.push_back(make_pair(ny, nx));
                            visit[ny][nx] = visit[cy][cx] + 1;
                        }
                    }
                }
            }
        }
     
        printf("%d", visit[n][m]);
     
        return 0;
    }
    		cs

연관 문제

  • 백준 13549 - 숨바꼭질3






    아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

</html>

댓글남기기

참고