2206_벽 부수고 이동하기 ( BFS )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다.

 

2206 벽부수고 이동하기

 - 이 문제는 단순한 미로찾기에서 벽을 부술 수 있는 기회가 1회 추가된 복합 문제이다

 - 단순히 접근하면 지도 전체에서 벽을 1번 부순 모든 경우의 수를 brute force 형태로  찾은 뒤 BFS로 각 경우마다 최단 거리를 구하여 결과를 도출할 수 있다

 - 하지만 그럴 경우 당연히 시간초과의 늪에 빠지게 된다.

 - 이에 대해 고민을 한 결과 벽을 부술 수 있는 상태 값을 만들어 문제를 해결하였지만 " 틀 렸 습 니 다 " 만 나왔을 뿐이다...ㅂㄷㅂㄷ

 - 여러 반례를 확인해본 결과 벽을 부수고 목적지까지 가다가 새로운 벽을 만났을때, 벽을 부수지 않고 목적지까지 가다가 새로운 벽을 만났을때에 대한 문제가 있었다. 반례는 아래 추가 내용을 참고하자

 - 문제 풀이는 BFS을 이용하여 해결하였다.

 - 자세한 내용은 코드의 주석을 참고하자

 

* 해당 문제는 글쓴이가 많이 헤맸던 문제기에 반례에 대한 추가 내용을 아래와 같이 첨부

 

반례

 - 벽을 먼저 부수고 목적지까지 가다가 새로운 벽을 만나 더이상 가지 못할때

 - 벽을 부수지 않았을 때와 벽을 부쉈을때 같은 경로를 지나간다는 가정 하에

 - 방문 확인 배열을 하나만 사용한다면, 한 경우에 의해 다른 경우가 진입을 못할 수가 있다.

 - 따라서 벽을 부수고 탐색 위치에 도달했는가? 와 벽을 부수지 않고 탐색 위치에 도달했는가?에 대한 두 상태에 대한 방문 확인 배열을 구성해주어야한다.

 - 자세한 내용은 코드의 주석을 참고하자

 

 

 

	//길목마다 벽이 세워져있을 수 있는 NxM 지도에서
	//최단 경로로 목적지에 도달했을때의 이동횟수를 구하는 문제
	//벽을 한번 부수고 이동할 수 있다는 가정이 있기에
	//NxM 행렬에 대해 벽을 한번 부순 모든 경우를 찾아
	//벽을 부수지 않은 경우와 벽을 부순 모든 경우 중
	//최단 경로의 값을 리턴하면 되는 문제
	//시간 복잡도를 계산해보고 문제에 접근하도록 하자
	//brute force 형태로도 답을 구할 순 있지만... 결과는 ㅎㅎ...
	#include <iostream> //io
	#include <queue> //queue
	#include <string> //string
	#include <tuple> //tuple
	using namespace std;
	//이미 부쉈다면 상태값 CRASH
	#define CRASH 1
	//아직 부수지 않았다면 상태값 NOT_CRASH
	#define NOT_CRASH 0
	//지도의 세로(N) 가로(M)크기를 받을 변수 선언 및 초기화
	int N = 0, M = 0;
	//초기 지도정보를 받을 배열 선언 및 초기화
	int map[1000][1000] = { 0 };
	//이미 방문한 위치를 확인할 배열 선언 및 초기화
	//check배열의 구성은 [y][x][carsh]로 구성된다
	//crash는 역할은 벽을 부수고 해당 지점(x,y)에 도착했느냐(1)와
	//벽을 부수지 않고 도착했냐(0) 두 상태를 가지기 위해서이다
	//이미 벽을 부수고 왔다면 이후 벽을 부술 수 없기에 더이상 나아갈 수 없고
	//벽을 부수지 않고 해당 지점에 도착했다면 추가로 벽을 부술 수 있기에 보다 나아갈 수 있다
	//각 배열의 원소는 방문하지 않았음(0)과 몇번의 걸음 끝에 방문하였음( n : 정수 )로 구성된다
	int check[1000][1000][2] = { 0 };
	//경로 탐색을 위한 방위 배열 선언 및 초기화
	int dx[4] = { 0, 1 , 0 ,-1 };
	int dy[4] = { -1, 0, 1, 0 };
	//최단거리의 값들을 저장할 배열 선언 및 초기화
	int res_arr[1000][1000] = { 0 };
	//최단거리의 값을 가질 변수 선언 및 초기화
	int res = 0;
	//최단 경로 탐색에 사용할 bfs 큐 선언
	//큐의 인자값은 x, y, crash(벽을 부쉈는가 부수지 않았는가)로 구성
	queue<tuple<int, int, int>> bfs_q;
	//return : 최단경로의 값, 만약 목적지에 도착 못했다면 -1 반환
	int find_path()
	{
	//탐색 시작 위치(x,y)와 아직 벽을 부수지 않았음(NOT_CRASH)을 삽입
	bfs_q.push(make_tuple(0, 0, NOT_CRASH));
	//벽을 부수지않고(NOT_CRASH) 시작 위치를 방문(1). 방문 값은 현재 이동 횟수( 초기 1 )를 의미
	check[0][0][NOT_CRASH] = 1;
	//탐색할 노드가 없을때까지 루프
	while (!bfs_q.empty())
	{
	//탐색 위치의 값과 해당 값에 대한 벽을 부순 여부(crash)값을 받아온다
	int x = get<0>(bfs_q.front());
	int y = get<1>(bfs_q.front());
	int crash = get<2>(bfs_q.front());
	//사용한 노드는 반환
	bfs_q.pop();
	//현재 위치가 목적지라면 이동한 횟수를 반환
	//crash는 목적지에 도착했을때까지 벽을 부쉈는가(NOT_CRASH)와 부수지 않았는가(CRASH) 두가지 상태로 받아올 수 있다
	//하지만 결론적으로는 return을 하게 되기에 가장 먼저 도착한 상태값의 결과를 반환하게 된다
	if (x == M - 1 && y == N - 1)
	return check[y][x][crash];
	//4방위에 대한 탐색 시작
	for (int i = 0; i < 4; i++)
	{
	//다음 탐색 위치를 설정
	int xn = x + dx[i];
	int yn = y + dy[i];
	//다음 탐색 위치가 탐색 범위를 벗어나면 스킵
	if (xn < 0 || xn >= M || yn < 0 || yn >= N) continue;
	//다음 탐색 위치에 벽이 있고, 아직 벽을 한번도 부수지 않았다면(NOT_CRASH)
	if (map[yn][xn] == 1 && crash == NOT_CRASH)
	{
	//다음 탐색 위치 값과 벽을 부수고 도착했음을 알려준다
	bfs_q.push(make_tuple(xn, yn, CRASH));
	//다음 위치에 벽을 부수고 갈 것이기에 방문 여부 배열은 yn, xn, CRASH으로 접근
	//현재까지 걸은 수 + 1을 넣어준다
	check[yn][xn][CRASH] = check[y][x][crash] + 1;
	}
	//다음 탐색 위치가 빈 공간이고, 아직 방문하지 않았다면
	if (map[yn][xn] == 0 && check[yn][xn][crash] == 0)
	{
	//다음 탐색 위치와 현재까지 벽을 부순 여부를 큐에 삽입
	bfs_q.push(make_tuple(xn, yn, crash));
	//다음 탐색 위치에 현재 걸음 수 + 1을 해준다
	check[yn][xn][crash] = check[y][x][crash] + 1;
	}
	}
	}
	return -1;
	}
	int main(void)
	{
	//지도의 크기 정보를 가져온다
	cin >> N >> M;
	//지도 정보를 삽입하기 위한 루틴
	for (int i = 0; i < N; i++)
	{
	string tmp_input;
	cin >> tmp_input;
	//문자열로 받을 것이기에 - '0'을 통해 정수값이 입력될 수 있도록 한다
	for (int j = 0; j < tmp_input.size(); j++)
	{
	map[i][j] = tmp_input[j] - '0';
	}
	}
	//탐색 시작
	res = find_path();
	//결과 출력
	cout << res << endl;
	return 0;
	}

view raw 2206_벽부수고이동하기.cpp hosted with ❤ by GitHub