문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
1. 문제해석
이 문제는 원래 벽을 지나가지 못하는 조건이었다면, 일반적인 BFS에서 벽일 때는 지나가지 못하고 거리 갱신을 못하고 지나가게끔 하면 되는 그런 기본문제에서 한단계 더 나아간 문제이다.
까다롭다고 느껴졌던 것은, BFS를 통해서 최단경로를 구할 수 있었던 것은 매 순간의 이동이 가장 짧은 경로라는 것이 보장되어있었기 때문인데, 이 경우에는 어떤 벽을 뚫느냐에 따라서 최단경로는 될 수 있어도 마지막 목적지에 도착할 수 있느냐 또한 문제가 되기 때문에, 단순히 벽을 뚫으면서 최단경로로만 갱신하는 것이 별 의미가 없다는 점이다.
기존 그래프 문제에서 달라지는 점이 벽 뚫기의 여부이므로, 최대 1번만 뚫을 수 있으므로 이것 또한 정보를 저장해야 한다는 것에 유념하였다. 큐에 저장할 때 거리, 벽 뚫은 횟수, 위치를 모두 저장하도록 했다.
그리고 BFS를 시작해서 한 노드의 인접 여부를 모두 조사할 때, 그 노드가 접근 가능한 인덱스(1이상 N이하 혹은 1이상 M이하)이라면, 벽인지 여부에 따라서 분기 해서
* 벽이 아니라면 : 1) ((위치), min(현재 경로, (이전 노드까지의 경로 + 1)) , 이전에 부순횟수) 를 큐에 넣고 2) 거리 갱신.
* 벽이라면:
* 벽을 부술 수 있다면 :
(특정 조건에 만족한다면):
- 1) ((((위치), min(현재 경로, (이전 노 드까지의 경로 + 1)) , 이전에 부순횟수 + 1) 을 큐에 넣고
- 2) 거리 갱신
* 벽을 부술 수 없다면 (이미 한번 부쉈다면)
그냥 지나감.하도록 짰다.
*특정 조건
그냥 벽을 뚫고 갈 수 있다고 해서 그 거리를 갱신하는 법은 정답이 아닐 것이라고 생각했기 때문에 추가한 조건이다.
보통의 조건으로는 최단 경로라는 조건이라면 갱신하면서 큐에 넣었을 텐데, 최단경로가 보장되는 것이 중요한 게 아니라 목적지에 도달하는 조건 또한 중요하므로, 이런 조건은 아닐 것이다.
오히려 벽을 부순 횟수를 최대한 적게 하면서 갱신하면 정답에 가까울 것이라는 직관을 가졌었다. (이를 가설로 둔다.)
(적게 뚫고서 갈 수 있다면 일단 목적지 도달하는 것이 좀 더 보장이 되기 때문에.)
왜 이렇게 하면 정답이 될 수 있을까? 정말 정답일까?
한번 알아보고자 했다.
1. 1. 예시
왼쪽 표가 맵이고 회색으로 칠해진 게 벽이다. 오른쪽 맵에는 (거리/ 부순횟수)가 저장된다.
오른쪽 맵에서 노란색 형광펜 칠이 되는 것이 벽을 부수는 시점이다. 부수지 않는 경우와 비교하기 위해 주황색으로 표시했다.
가독성을 위해 모든 경우를 표현하지는 않았다.
첫번째 줄의 1번 케이스를 보면, (2,1)위치에서 초록색으로 써놓았듯이 어떤 값을 거리로 저장할지 고민할 때, 부수고 들어간 경우가 거리도 더 길었기 때문에 파란색을 택해야 한다는 것이 바로 보인다.
두번째 줄의 2번 케이스를 보면, 초반에 마주치는 회색 벽은 부수든 안부수든 최단경로에는 영향을 주지 않지만,
막바지에 도착점에 도달하기 위해서는 회색벽을 부순 케이스는 목적지에 도달조차 하지 못하게 된다.
예시를 적용해서 한번 문제를 풀어보았다. 우선 가설 상 틀린 케이스는 둘 다 아니었다.
1.2. 논리
<반례>
4 6
010100
010110
000110
111110이 예시가 위의 논리에는 맞지 않는다.
벽을 뚫고 가거나 벽을 뚫지 않고 가는 경우를 두가지 갈래로 가지 않고 오직 하나만 한다면 문제가 될 수 있다는 걸 알 수 있다.
이 문제 또한 너무 어려워서 다른 사람들이 어떻게 풀었는지 확인하고 왔다.
기본적인 생각은 이런 것이다.
벽을 부순 횟수를 세면서 하는 것이 아니라 어차피 1번만 부술 수 있는 것이므로,
한번 부순 후로는 다음 벽을 만나면 멈춘다. 그니까 한번 부수고 도달한 벽돌이라면, 저장하고 이동하면서 벽이 아닐 동안에만 최단 경로를 갱신하면서 이동한다.
어떤 블로거는 이를 이렇게 표현했다.
한번도 부수지 않고 이동하는 경우를 '0의 세계',
한번 부수고 이동하는 경우를 '1의 세계'라고 하면, '0의 세계'에서 움직이다가 벽을 만나느냐, 만나지 않느냐에 따라 '0의 세계'에 머무르거나 '1'의 세계'로 이동해서 움직일 수 있다.
하지만 '1의 세계'에서 이동중이라면, 다시 '0의 세계'로 돌아갈 수 없고 벽돌을 만나면 멈춰버린다.
그렇기 때문에 두가지의 세계로 나누어 최단 경로를 갱신하며 움직이면,
최단 경로를 알 수 있다.
2. 주의점
'0의 세계'에서 최단경로에 성공했는지, '1의 세계'에서 최단경로에 성공했는지는 모른다. 따라서 distance 배열을 나중에 접근할 때는 분기해서 최단경로를 알 수도 있지만, 따라서 BFS를 하는 동안 Queue에서 pop한 노드가 원하는 목적지라면 그때 pop된 정보에서 거리를 return 하는 식이 좋다.그리고 queue가 빌 때까지 BFS를 진행했는데도 목적지 노드를 못 만났다면 -1를 return 하는 것이다.
3. 구현
구현한 코드는 다음과 같다.
#include <iostream>
#include <queue>
#include <utility>
#define TRUE 1
#define FALSE 0
#define INF 1987654
using namespace std;
int N,M;
int map[1001][1001];
int dist[1001][1001][2];
int visited[1001][1001][2] = {0,};
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
queue < pair<int , pair<pair<int,int>,int> > > Q;
int Cango(int r, int c )
{
if(1<=r&&r<=N &&1<=c&&c<=M)
return 1;
return 0;
}
void input()
{
char str[1001];
char *ptr;
for(int i=1;i<=N;i++)
{
scanf("%s", str);
ptr = str;
for(int j=1;j<=M;j++)
{
map[i][j] = *(ptr ++) - '0';
// printf("%d ",map[i][j]);
}
// printf("\n");
}
}
int BFS()
{
while(!Q.empty()) {
int dis = Q.front().first;
int r = Q.front().second.first.first;
int c = Q.front().second.first.second;
int crash = Q.front().second.second;
Q.pop();
if (visited[r][c][crash] == TRUE)
continue;
visited[r][c][crash] = TRUE;
if(r==N && c ==M)
return dis;
// printf("node (%d,%d) dis %d in BFS %d\n", r,c, dis,crash );
for (int i = 0; i < 4; i++) {
int next_r = r + dir[i][0];
int next_c = c + dir[i][1];
if (Cango(next_r, next_c)) {
// printf("next: (%d,%d) - ", next_r, next_c );
if (map[next_r][next_c] == 1) //벽을 만났다면, 부술 수 있어야 갱신을 한다.
{
if (crash == 0 && visited[next_r][next_c][0] == FALSE) {
// printf("%d in [1] push\n", dis+1);
dist[next_r][next_c][1] = dis + 1;
Q.push(make_pair(dis + 1, make_pair(make_pair(next_r, next_c), 1)));
}
}
else if (crash == 0 && visited[next_r][next_c][0] == FALSE) //벽이 아니다. 그리고 아직 한번도 안부쉈다 -> 0세계에 기록.
{
// printf("%d in [0] push \n", dis+1);
dist[next_r][next_c][0] = dis + 1;
Q.push(make_pair(dis + 1, make_pair(make_pair(next_r, next_c), 0)));
}
else if (crash == 1 &&
visited[next_r][next_c][1] == FALSE)//벽이 아니다. 그리고 한번 부순 적이 있다. -> 갈 ㅜㅅ 있고, 1세계에 기록.
{
// printf("%d in [1] push \n", dis+1);
dist[next_r][next_c][1] = dis + 1;
Q.push(make_pair(dis + 1, make_pair(make_pair(next_r, next_c), 1)));
}
}
}
}
return -1;
}
int find()
{
dist[1][1][0] = 1;
Q.push(make_pair(1, make_pair(make_pair(1,1),0)));
return BFS();
}
void print_dist()
{
printf("\n\t distance \n");
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
printf("%d ", dist[i][j][0]);
}
printf("\n");
}
printf("\n\t distance crash \n");
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
printf("%d ", dist[i][j][1]);
}
printf("\n");
}
}
int main()
{
scanf("%d %d", &N, &M);
input();
printf("%d", find());
// print_dist();
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
| 백준 1181번 - 단어 정렬 , c++ sort함수 (5) | 2023.01.09 |
|---|---|
| 백준 2805번: 나무자르기 - 이분탐색 (0) | 2023.01.08 |
| 백준 1753번: 최단경로 ( 최단경로, 다익스트라) (0) | 2022.12.30 |
| 백준 16928번 :뱀과 사다리 게임 (그래프 순회 및 탐색) (2) | 2022.12.29 |
| 백준 1912- 연속합(다이나믹 프로그래밍) (0) | 2022.12.29 |