N•M의 행렬로 표현되는 맵이 주어진다.
맵은 0과 1로 이루어져 있으며 '0'은 이동할 수 있는 곳 '1'은 벽을 의미한다.
(0, 0)부터 시작하여 (N-1, M-1)의 위치까지 이동하는 최단 거리를 구해야 한다.
이때 상하좌우로 이동할 수 있으며, 벽은 한 개까지 부수며 이동할 수 있다.
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000) (1 ≤ M ≤ 1,000)
다음 줄에는 N개의 줄에 M개의 숫자가 주어진다.
예제 입력
6 4
0100
1110
1000
0000
0111
0000
예제 출력
15
어디서 힌트를 얻을 수 있을까?
'행렬', '최단 경로'를 통해 이 문제가 BFS를 이용하여 문제를 풀 수 있다는 것을 알 수 있다.
우선 최단 경로란 한 번 방문한 노드는 방문하지 않고 갈 수 있는 경로를 의미한다.
그렇기 때문에 보통 BFS 문제를 풀 때 방문 여부를 확인하는 cache 배열을 이용한다.
하지만 이 문제는 벽을 부실 수 있는 조건이 붙어있다. 즉, 다음의 두 가지 조건을 검사해야 한다.
이 두 가지를 검사하면서 BFS를 작성하면 오류가 날 일이 없다.
#include <iostream>
#include <queue>
#include <string>
int board[1001][1001];
int N, M;
int cache[1001][1001][2];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
struct Point {
int x;
int y;
int r;
int crash;
};
bool isInBoard(int y, int x)
{
return y >= 0 && y < N && x >= 0 && x < M;
}
bool isWall(int y, int x)
{
return board[y][x];
}
bool isVisited(int y, int x, int crash)
{
return cache[y][x][crash];
}
int bfs(void)
{
std::queue<Point> pq;
cache[0][0][0] = 1;
cache[0][0][1] = 1;
pq.push(Point({0, 0, 1, 0}));
while (!pq.empty())
{
int currX = pq.front().x;
int currY = pq.front().y;
int currR = pq.front().r;
bool currCrash = pq.front().crash;
pq.pop();
if (currX == M - 1 && currY == N - 1)
return currR;
for (int i = 0; i < 4; i++)
{
int nextX = currX + dx[i];
int nextY = currY + dy[i];
int nextR = currR + 1;
if (isInBoard(nextY, nextX) && !isVisited(nextY, nextX, currCrash))
{
if (isWall(nextY, nextX))
{
if (!currCrash)
{
pq.push(Point({nextX, nextY, nextR, 1}));
cache[nextY][nextX][1] = 1;
}
}
else
{
pq.push(Point({nextX, nextY, nextR, currCrash}));
cache[nextY][nextX][currCrash] = 1;
}
}
}
}
return -1;
}
int main(void)
{
std::cin >> N >> M;
std::string str;
for (int i = 0; i < N; i++)
{
std::cin >> str;
for (int j = 0; j < M; j++)
board[i][j] = str[j] - '0';
}
std::cout << bfs() << std::endl;
return 0;
}
https://www.acmicpc.net/problem/2206
백준 2407 - 조합(C++) (0) | 2023.05.26 |
---|---|
백준 2263 - 트리의 순회(C++) (0) | 2023.05.26 |
백준 2096 - 내려가기(C++) (0) | 2023.05.24 |
백준 1991 - 트리 순회(C++) (2) | 2023.05.24 |
백준 1967 - 트리의 지름(C++) (0) | 2023.05.24 |