백준 2206 : 벽 부수고 이동하기 C++

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

2206번: 벽 부수고 이동하기

후기겸 풀이

 

1. 처음에 입력받을때 map[i][j]가 1인 좌표들을 wall 이라는 vector로 만들고, 순서대로 하나씩 벽 없애고 BFS 돌리니까 바로 시간초과 뜨더라....ㅎ

 

2. 그래서 구글링으로 벽 부순상태인지 아닌지 확인용 flag 추가하는 풀이 확인!

 -> visited도 벽을 부순 상태랑 안부순 상태 구분!

 -> int visit[1000][1000][2]; // 0이면 부순 상태 1이면 안부순 상태

1) 벽을 안부순 상태

 벽을 만나면 : 벽 부수고 flag =1로 만들고 이어서

 벽 아니면 : 그냥 BFS

 

2) 벽을 부순상태 (flag =1)

 벽만나면 : 그냥 패쓰

 벽 아니면: BFS

 

 

3. 아니 다 풀었는데 100%에서 틀렸습니다 떠서 혼자 해맸다

 입력이

1 1

0 일때 예외처리 해야되더라 

 

if (m == 1 && n == 1)
answer = 1;

-> 추가!

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

struct wall {
	int r, c, flag;
};

int map[1000][1000];
int visit[1000][1000][2]; // 마지막 1이면 벽 부순거 0이면 아직 벽 안부순 상태

int d_r[4] = { 0,0,1,-1 };
int d_c[4] = { 1,-1,0,0 };

int n,m;
int answer = 987654321;

void bfs() //0,0 에서 n,m까지!
{
	queue<wall> q;
	q.push({ 0,0,0 });
	visit[0][0][0] = 1;

	int result = 2;
	while (!q.empty())
	{
		int s = q.size();
		for (int h = 0; h < s; h++)
		{
			int flag = q.front().flag;// 1이면 벽 한번 부순상태, 0 이면 아직 한번도 안부순 상태
			int r = q.front().r;
			int c = q.front().c;
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int flag2 = flag;
				int new_r = r + d_r[i];
				int new_c = c + d_c[i];

				if (new_r == n - 1 && new_c == m - 1)//도착지
				{
					answer = result;
					return;
				}

				if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= m)//지도밖
					continue;
				if (flag2 == 1)//벽 한번 부순 상태
				{
					if (map[new_r][new_c] == 1)//벽만났으면
						continue;
					if (visit[new_r][new_c][1])//이미 방문한 곳이면
						continue;

					visit[new_r][new_c][1] = 1;
				}
				else
				{
					if (visit[new_r][new_c][0])//이미 방문한 곳이면
						continue;

					if (map[new_r][new_c]==1)
					{ //벽이면 부수고, 벽 부순 경우 방문 맵에 체크 
						flag2 = 1;
						visit[new_r][new_c][1] = 1;
					}
					else
						visit[new_r][new_c][0] = 1;
				}

				q.push({ new_r,new_c,flag2 });
			}
		}

		result++;

	}

}

int main()
{
	string a;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		for (int j = 0; j < m; j++)
		{
			map[i][j] = a[j] - '0';
		}
	}

	bfs();

	if (answer == 987654321)
		answer = -1;

	if (m == 1 && n == 1)
		answer = 1;

	cout << answer << endl;
	return 0;
}