M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 2206 - 벽 부수고 이동하기

최대 1 분 소요

문제

백준 2206 - 벽 부수고 이동하기 풀러가기

문제 분석

N,M으로 가는 가장 적은 칸 수 를 구하는 문제로, 가중치가 1인 BFS로 문제를 풀 수 있다.

이때, 벽이 있는 경우에는 최소 한 번 벽을 뚫을 수 있으므로 벽을 뚫은 경우와, 뚫지 않은 경우를 포함하여 3가지 정보를 포함한 것을 한 정점으로 볼 수 있다.

  • (4,5)는 (4,5,0)과 (4,5,1)의 정점 두개로 볼 수 있다.

문제 풀이

  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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include<cstdio>
    #include<queue>
    #include<tuple>
    #include<algorithm>
     
    using namespace std;
     
    int map[1000][1000];
    int visit[1000][1000][2];
    queue <tuple<int, int, int>> q;
     
    int dy[] = { 0, 0, 1, -1 };
    int dx[] = { 1,-1,0,0 };
     
    int main() {
        int n, m;
     
        scanf("%d %d", &n, &m);
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%1d", &map[i][j]);
            }
        }
     
        visit[0][0][0] = 1;
        q.push(make_tuple(0,0,0));
     
        while (!q.empty()) {
            int cy = get<0>(q.front());
            int cx = get<1>(q.front());
            int w = get<2>(q.front());
     
            q.pop();
     
            for (int k = 0; k < 4; k++) {
                int ny = cy + dy[k];
                int nx = cx + dx[k];
     
                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    
                    if (map[ny][nx] == 0 && visit[ny][nx][w] == 0) {
                        visit[ny][nx][w] = visit[cy][cx][w] + 1;
                        q.push(make_tuple(ny, nx, w));
                    }
     
                    if (w == 0 && map[ny][nx] == 1 && visit[ny][nx][w+1] == 0) {
                        visit[ny][nx][w+1] = visit[cy][cx][w] + 1;
                        q.push(make_tuple(ny, nx, w+1));
                    }
                }
            }
        }
     
        if ((visit[n-1][m-1][0] != 0 ) && visit[n - 1][m - 1][1] != 0) {
            printf("%d", min(visit[n - 1][m - 1][0], visit[n - 1][m - 1][1]));
        }
        else if(visit[n - 1][m - 1][1] != 0){
            printf("%d", visit[n - 1][m - 1][1]);
        }
        else if (visit[n - 1][m - 1][0] != 0) {
            printf("%d", visit[n - 1][m - 1][0]);
        }
        else {
            printf("-1");
        }
     
        return 0;
    }
    		cs
  • 1
    2
    int visit[1000][1000][2];
    queue <tuple<int, int, int>> q;
    		cs
    • 행, 열 그리고 벽을 뚫었는지 안뚫었는지에 대한 총 3가지로 구성되어있다.
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    if (map[ny][nx] == 0 && visit[ny][nx][w] == 0) {
        visit[ny][nx][w] = visit[cy][cx][w] + 1;
        q.push(make_tuple(ny, nx, w));
    }
     
    if (w == 0 && map[ny][nx] == 1 && visit[ny][nx][w+1] == 0) {
        visit[ny][nx][w+1] = visit[cy][cx][w] + 1;
        q.push(make_tuple(ny, nx, w+1));
    }
    		cs
    • 다음에 있는 곳이 벽이 아니라면 그냥 가면 되지만
    • 다음에 있는 곳이 벽이라면, 벽을 한번도 뚫지 않은 경우에만 갈 수 있다.





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

댓글남기기

참고