알고리즘 문제/BOJ
2206번 벽 부수고 이동하기
parkit
2018. 8. 21. 23:58
728x90
반응형
처음 문제를 보았을 때는 난감했다.
'어떻게 하면, 어떤 위치에 있는 벽을 부수었는지, 안 부수었는지 여부를 알 수 있을까' 라고 생각했다.
위의 생각은 visit(방문 여부)를 하나로만 생각해서 그렇다.
즉, 벽을 부수었을 때의 방문 여부, 벽을 안 부수었을 때의 방문 여부 2가지로 나누어서 생각해야 한다.
어떻게 보면, 벽을 하나 하나 부수면서 경우의 수를 따지는 것이다.
https://www.acmicpc.net/problem/2206
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include <iostream> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <string> #include <math.h> #include <algorithm> using namespace std; bool visit[2][1001][1001] = { false, }; // visit[0]~ : 벽 안 부숨, visit[1]~ : 벽 부숨 int map[1001][1001] = { 0, }; int dy[4] = { -1, 0, 1, 0 }; int dx[4] = { 0, -1, 0, 1 }; int N = 0, M = 0; queue<pair<int, pair<int, int> > > q; int BFS() { q.push({ 0, {1, 1} }); // 문제 조건에 의해 (1, 1)에서 출발하고, 벽은 당연히 안 부순 상태(0) visit[0][1][1] = true; // 벽 안 부순 상태 + (1, 1) 방문 표시 int ret = 1; // 시작하는 칸도 포함해야 하기 때문에 1부터 시작.(문제 조건) while (!q.empty()) { int qSize = q.size(); while (qSize--) { int current = q.front().first; int r = q.front().second.first; int c = q.front().second.second; q.pop(); if (r == N && c == M) // 도달 했다면 { return ret; } for (int i = 0; i < 4; i++) { int y = r + dy[i]; int x = c + dx[i]; if (y <= 0 || y > N || x <= 0 || x > M || visit[current][y][x]) continue; if (current == 0) // 지금까지 벽을 안 부수었다면 { if (map[y][x] == 1) // 벽이라면 부순다. { q.push({ 1, {y, x} }); // 부수었으니 1로 바꿔준다. visit[1][y][x] = true; } else if (map[y][x] == 0) // 벽이 아니라면 그냥 통과 { q.push({ 0, { y, x } }); visit[0][y][x] = true; } } else if (current == 1) // 벽을 부순 적이 있다면 { if (map[y][x] == 0) // 벽을 통과하지 못 한다. { q.push({ 1, { y, x } }); visit[1][y][x] = true; } } } } ++ret; } return -1; // 도달 실패 } int main(void) { scanf("%d %d", &N, &M); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { scanf("%1d", &map[i][j]); } } printf("%d\n", BFS()); return 0; } | cs |
728x90
반응형