문제
미로에서 최단 경로로 빠져나가자! 한 번은 벽 뚫어도 된당
생각
최단 경로니까 BFS,
벽을 뚫었었는지, 지나온 곳인지 알면서 길 찾아가자~~
시도 1
큐에 벽 부신적 있는지, 지금까지 얼마나 이동했는지, 위치를 저장하고,
queue<pair<int, pair<int, pair<int, int>>>> q;지나온 길은 받은 맵 정보를 담아놓은 배열값을 1로 바꿨다.
map[nextx][nexty] = 1;문제! 이게 벽을 부시고 온 곳인지, 그냥 벽인지를 몰라 (굉장 멍청)
시도 2
지나온 길을 2값으로 바꿔줌
map[nextx][nexty] = 2;틀렸다고 함..!!
생각해보니 이게 여러번 탐색을 막기위해 이런짓을 하는거구
0값인 map만 갈 수 있게 짜다보니 발생한 문제인데
'벽을 안 뚫고 지나가는 애'
'벽을 뚫고 지나가는 애'
두 아이가 같은 map 위치를 지나갈 수 있다!!
(예를 들어 한 곳에 길을 뚫은 애가 지나가서 2로 만들어버리면
빙돌아온 애가 그 위치를 못 지나가..
엥? 근데 최단거리니까 뒤에 오는 애는 생각안해두대자나! 가 아니구
도착지 근처가 다 벽으로 둘러쌓여있으면 나중에 돌아온 애가 벽 뚫고 도착하겠지~~
이거 몰라서 머리 끙끙..ㅜ)
성공
int map[1000][1000];
// 0 아무도 안 지나감 1 벽 2 벽 안 뚫고 지나감 3 벽 부시고 지나감 4 둘 다 지나감이렇게 맵에 표시해 놓고
queue<pair<int, pair<int, pair<int, int>>>> q;
pair<int, pair<int, pair<int, int>>> temp;
//문 부신적있니?, 지금까지 걸은 거리, 줄, 숫자탐색하는 애들을 저장하면서 BFS!
실수했던 논리들
map이 0(처음 지나가는 길)일 땐 상태 안 보고 그냥 2로 바꿨었음
뚫을 때 벽(1)을 3으로 만들었었음(벽이 벽이 아니게돼)
메모리 초과, 틀렸습니다, 데이터 추가 후 틀렸습니다 등 여러 고난을 겪었음ㅋㅋㅋ웃기다
주절주절
이렇게 이상하게 코드 짜는 사람 나밖에 없는 것 같아서
다른 사람들 코드도 봤는데
위치 상태 저장을 하는 3차원 배열을 만들어서 하는 사람들이 대부분인 것 같다
예)
check[MAX][MAX][2] //3차원 배열을 만들어서 관리근데 나는 추가적인 배열을 만들거나, 큐에 같이 정보 넣고 계속 같이 다니는 걸 싫어해서
그냥 map 정보 받아놓은 곳에 2 3 4 같이 내 마음대로 정해서 값 바꿔서 사용한다
//주석으로 무슨 상태인지는 설명해준다
이게 나쁜지 좋은지는 머르겠는데.. 나의 특징 아닐까 히히
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
queue<pair<int, pair<int, pair<int, int>>>> q;
pair<int, pair<int, pair<int, int>>> temp;
//문 부신적있니?, 지금까지 걸은 거리, 줄, 숫자
int map[1000][1000];
// 0 갈 수 있음 1 벽잇음 2 그냥 지나옴 3 벽 부시고 지나옴 4 둘 다 지나감
int n, m;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0 ,0 };
void go(int nextx, int nexty, int nowdis, int nowstate) {
if (map[nextx][nexty] == 0) {
//한번도 안 지나간 그냥 갈 수 있는 곳이면
if (nowstate == 0) {
//벽 한번도 안 뿌순애 지나갑니다~
map[nextx][nexty] = 2;
}
else {
//벽 부셨던 애 지나갑니다~
map[nextx][nexty] = 3;
}
q.push(make_pair(nowstate, make_pair(nowdis + 1, make_pair(nextx, nexty))));
}
else if (map[nextx][nexty] == 1) {
//벽이면
if (nowstate == 0) {
//한번도 벽 부신적 없음 == 벽 부시고 가봐!
q.push(make_pair(1, make_pair(nowdis + 1, make_pair(nextx, nexty))));
}
}
else if (map[nextx][nexty] == 2) {
//전에 그냥 온길 부시고 온 애는 지나가게 해쥬자
if (nowstate == 1) {
map[nextx][nexty] = 4;
q.push(make_pair(1, make_pair(nowdis + 1, make_pair(nextx, nexty))));
}
}
else if (map[nextx][nexty] == 3) {
//전에 벽 부시고 왔어? 그냥 지나가는 애는 지나가게 하쟝
if (nowstate == 0) {
map[nextx][nexty] = 4;
//지나간 길이니까 벽아닌 길임 0
q.push(make_pair(0, make_pair(nowdis + 1, make_pair(nextx, nexty))));
}
}
}
int findRoad() {
int tx, ty, nx, ny;
map[0][0] = 2;
q.push(make_pair(0, make_pair(1, make_pair(0, 0))));
while (1) {
temp = q.front();
tx = temp.second.second.first;
ty = temp.second.second.second;
if (tx == n - 1 && ty == m - 1) {
return temp.second.first;
}
for (int i = 0; i < 4; i++) {
nx = tx + dx[i];
ny = ty + dy[i];
if (nx >= n || ny >= m || nx < 0 || ny < 0) {
continue;
}
go(nx, ny, temp.second.first, temp.first);
}
q.pop();
if (q.empty()) {
return -1;
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &map[i][j]);
}
}
cout << findRoad();
return 0;
}