[백준알고리즘] 2206번 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

어제 푼 문제랑 유사한 형태!

풀이가 거의 비슷하기 때문에 자세하게 설명한 https://j2wooooo.tistory.com/39 이 풀이를 참고하기를!!!

bfs로 푸는 방식!

벽을 부쉈는지 여부를 넣어주어야 하기 때문에 visited를 3차원 배열로 만들어야 한다!

**내가 실수했던 부분**

1) string 넣을 때, 문제 제대로 안 보고 string으로 안 넣었었다..ㅠ

2) string 넣을 때, 배열은 (1,1)부터 string은 [0]부터 넣어주었어야 했는데 이 부분을 간과했었다...

3) 값에 따른 조건문 처리할 때, 조건문의 순서를 다르게 해서 원하는 것과 다른 상황이 도출되었다..

앞으로 신경써서 코딩하자!!!!!!!!!!!!!

#include<iostream>
#include<queue>
#include<string>
using namespace std;
int N, M;
int ans = 1;
bool flag;
char map[1001][1001];
int visited[1001][1001][2];
queue<pair<pair<int, int>, int>>q; // x좌표, y좌표, 한번 벽을 부쉈는지 여부
int dx[4] = { 0,0, -1,1};
int dy[4] = { -1,1,0,0 };
int main(void)
{
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++)
	{
		cin >> str;
		for (int j = 1; j <= M; j++)
		{
			map[i][j] = str[j-1];
		}
	}
	q.push(make_pair(make_pair(1, 1), 0));
	visited[1][1][0] = true;
	while (!q.empty())
	{
		int qsize = q.size();
		while (qsize--)
		{
			int x = q.front().first.first;
			int y = q.front().first.second;
			int gowall = q.front().second;
			q.pop();
			if (x == N && y == M) {
				flag = true;
				break;
			}
			for (int i = 0; i < 4; i++)
			{
				int mx = x + dx[i];
				int my = y + dy[i];
				int ngowall = map[mx][my]-'0';
				if (mx >= 1 && mx <= N && my >= 1 && my <= M)
				{
					if (ngowall && gowall) continue; // 이미 벽을 부쉈는데 또 부숴야 하면 continue
					ngowall = (ngowall || gowall); // 벽 부순 여부 갱신
					if (visited[mx][my][ngowall]) continue; // 벽 부순 여부에 따른 좌표 방문 여부 확인 후, 이미 방문했었으면 continue
					visited[mx][my][ngowall] = true;
					q.push(make_pair(make_pair(mx, my), ngowall));
				}
			}
		}
		if (flag) break;
		ans++;
	}
	if (flag) cout << ans;
	else cout << -1;
	return 0;
}