M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 2178 - 미로 탐색

최대 1 분 소요

문제

백준 2178 - 미로 탐색 풀러가기

문제 분석

1,1에서 m,n으로 가는 최소 칸 수 를 구하는 문제로, bfs를 이용할 수 있다.

문제 풀이

  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
    #include <cstdio>
    #include <queue>
     
    using namespace std;
     
    int n, m;
     
    int maze[101][101];
    int visit[101][101];
     
    int dx[] = { 1,0,0,-1 };
    int dy[] = { 0,1,-1,0 };
     
    queue<pair<int, int>> q;
     
    void bfs() {
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
     
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
                if ((0 < nr && nr <= n) && (0 < nc && nc <= m)) {
                    if (maze[nr][nc] == 1 && visit[nr][nc] == 0) {
                        visit[nr][nc] = visit[cr][cc] + 1;
                        if (nr == n && nc == m) {
                            return;
                        }
                        q.push(make_pair(nr, nc));
                    }
                }
            }
            q.pop();
        }
    }
     
    int main() {
        
        scanf("%d %d", &n, &m);
     
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%1d", &maze[i][j]);
            }
        }
     
        q.push(make_pair(1,1));
        visit[1][1] = 1;
        bfs();
     
        printf("%d", visit[n][m]);
     
        return 0;
    }
    		cs
    • 8~9번째 : 위치 (1,1)을 배열에서도 [1] [1]에 접근하고 싶어서 size를 [101] [101]로 잡았다.

  2. bfs 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void bfs() {
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
                if ((0 < nr && nr <= n) && (0 < nc && nc <= m)) {
                    if (maze[nr][nc] == 1 && visit[nr][nc] == 0) {
                        visit[nr][nc] = visit[cr][cc] + 1;
                        if (nr == n && nc == m) {
                            return;
                        }
                        q.push(make_pair(nr, nc));
                    }
                }
            }
            q.pop();
        }
    }
    		cs
    • 11번째 : 다음 번 row와 column의 값이 n, m과 같다면 문제에서 목표한 바를 이룬 것 이므로 bfs 함수를 종료한다.

연관 문제






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

댓글남기기

참고