백준 2206 벽 부수고 이동하기 [C++]

작성일 | In |

Problem : 벽 부수고 이동하기

유형 : BFS

문제 해석

  • 목적지까지 이동하는 최단 경로를 구하라.
    • 시작지점 은 항상 {1,1} 이다.
    • 이동하는 도중에 한개의 벽을 부실 수 있다.

해결 전략

  • 3차원 배열로 관리한다.
    • [x 좌표][y 좌표][스킬 사용 여부]
    • 스킬을 사용할 수 있는 상태에서, 벽을 만난 경우, 스킬을 사용하고 해당 위치로 이동한다.
    • 스킬을 사용하지 않은상태와, 사용한 상태를 분리해서 이동시킨다.
      • 왜냐하면, 스킬 사용여부에 따라서 경로가 달라지기 때문이다.

설계, 구현

  • {시작점, 도착점, 스킬사용여부 (0이면 사용X 1이면 사용O)} 를 구조체로 관리한다.
  • 방문 여부와, 이동거리를 한번에 처리하기 위해서 dist 배열을 -1 로 초기화 한다.
  • BFS를 진행한다.
    • 벽을 만난경우 스킬을 쓸 수 있다면 쓴다.
      • 스킬을 사용했으므로 상태 여부를 바꾸어서 계속 탐색시킨다.
      • 스킬을 사용하고, 지금까지 왔던 길을 되돌아 갈 수 도 있다.
        • 하지만, 해당 방법으로는 절대 최단경로에 도달하지 않으므로 신경쓰지 않아주어도 된다.
        • 물론 스킬 사용하기 전까지의 경로를 가지 못하게 처리해주어도 똑같이 답이 나온다.
  • 정답을 낸다.

주의할 점

  • 시작할때의 위치도 1로 센다. 0 스타트가 아니다.

코드

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;

int n, m;

int board[1002][1002];
int dist[1002][1002][2];

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

const int CANT_GO = -1;

struct st {
    int x;
    int y;
    int skill;
};

int getAnswer() {
    int nonSkill = dist[n - 1][m - 1][0];
    int useSkill = dist[n - 1][m - 1][1];

    if (nonSkill == CANT_GO) return useSkill;
    else if (useSkill == CANT_GO) return nonSkill;
    else return min(nonSkill, useSkill);
}

void bfs() {
    queue<st> q;
    dist[0][0][0] = 1;
    q.push({ 0,0,0 });

    while (!q.empty()) {
        st cur = q.front(); q.pop();
        int curDist = dist[cur.x][cur.y][cur.skill];

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (board[nx][ny] == 1 and cur.skill == 0) {
                if (dist[nx][ny][1] != -1) continue;
                dist[nx][ny][1] = curDist + 1;
                q.push({ nx,ny,1 });
            }
            if (board[nx][ny] == 0) {
                if (dist[nx][ny][cur.skill] != -1) continue;
                dist[nx][ny][cur.skill] = curDist + 1;
                q.push({ nx,ny,cur.skill });
            }
        }
    }
}

void solve() {
    bfs();
    cout << getAnswer() << "\n";
}

void init() {
    memset(dist, -1, sizeof(dist));
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        for (int ii = 0; ii < m; ++ii) {
            board[i][ii] = line[ii] - '0';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    init();
    solve();

    return 0;
}

피드백

  • BFS 문제도 오랜만에 풀어보니, 생각보다 구현 속도가 빠르게 나오지 않았다.
    • 역시 알고리즘은 꾸준히 가 답인것 같다.