백준 2178. 미로 탐색[실패]

1.실패 원인

늘 조건 하나 때문에 실패한다.. 근데 그 조건이 문제의 핵심인지라 더 괴롭다.. 

이 문제는 bfs문제로 (0,0) 에서 출발하여 (N-1,M-1) 까지 갈 수 있는 경로중 최단 경로를 찾아내는 것이다.

문제의 핵심 부분은 분기가 생기는 부분이다. 분기가 생겼을 때 최소 거리를 비교하려면 분기된 부분을 기점으로

새로운 카운팅 변수를 추가해줘야 한다. 분기가 100번 생겼다고 하면 골치가 아프다..

처음에 코드를 작성할 때 리스트를 이용해서 풀 생각을 했었다. 리스트로 노드를 이어나가다가 분기가 생기면

리스트를 관리하는 벡터에 새로운 리스트를 추가하여 여러 방향의 노드들을 연결할 수 있도록 하는것이다.

 

예를 들어서 

 

101111

101010

101011

111011

 

이 맵에서 [5,1] 지점에서 분기가 일어난다. 이 때 [5.1] 지점까지의 모든 경로가 담긴 리스트를 새로운 리스트에 복사하고

새로운 리스트를 벡터에 담은 후 분기별로 진행을 하는 것이 처음의 아이디어였다. 나름 괜찮아 보였는데 반복 구간에서 문제가 생겼다. 분기가 생길 때 리스트를 생성해야하는데 4방향에 대해서 생성할 타이밍 잡기가 너무 어려웠다. 2방향 이상으로 진행 가능할 때 카운트 수와 방향을 변수로 받고 카운트 수만큼 리스트가 생성되고 .. 최악에 상황에 리스트 수가 너무 많아지고 리스트에 큐에.. 답도없는 상황이 생길것을 예감하여 그만두었다 ㅠㅠ..

 

2.작성 코드

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

int N, M;

int arr[101][101];
bool bvisit[101][101] = { false, };

int DIRX[4] = { -1,0,1,0 };
int DIRY[4] = { 0,1,0,-1 };

struct coord {
	int x;
	int y;
	
};
int check[101][101] = { 0, };

queue<coord> q;
void bfs() {
	int startX = 0;
	int startY = 0;
	coord c;
	c.x = startX;
	c.y = startY;
	q.push(c);
	bvisit[0][0] = true;
	while (!q.empty()) {
		coord mycoord = q.front();
		int mx =mycoord.x;
		int my =mycoord.y;
		
		q.pop();
	
			for (int i = 0; i < 4; i++) {
				int nextX = mx + DIRX[i];
				int nextY = my + DIRY[i];

				if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N && !bvisit[nextY][nextX] 
					&& arr[nextY][nextX] == 1 && check[nextY][nextX]==0) {
					check[nextY][nextX] = check[my][mx] +1;
					coord nextCoord;
					nextCoord.x = nextX; nextCoord.y = nextY;
					q.push(nextCoord);
				}
			}

	}
}




int main() {

	
	cin >> N >> M;
	for(int y=0; y<N;y++)
		for (int x = 0; x < M; x++)
		{
			scanf("%1d", &arr[y][x]);
		}

	bfs();
	cout << check[N - 1][M - 1]+1 << endl;
		

	return 0;
}

3.참고 코드

https://sihyungyou.github.io/baekjoon-2178/

백준 2178번 : 미로 탐색

 

4. 해결 방안

핵심을 찾아내는 것이 너무 어렵다. 참고용 코드를 보면 진짜 간단한 아이디어로 풀어내셨다..

처음에는 M,N에 도착했을 때 조건을 종료해야하지 않나 생각 했었는데 도착 위치까지 하나씩 탐색하여

진행하는 과정이 BFS임을 잊고있었다. 결국 여러 리스트를 생성하여 복사하고 이어붙인다는 생각은

처음부터 잘못됐었고.. 배열 하나를 더 만들어 현재의 위치까지의 경로는 지난 경로 +1 이라는 

간단한 공식을 이용하면 결국 마지막 탐색에서 경로 수를 구할 수 있다.

 

최소 거리에 목메달았었는데 BFS에서는 결국 가장 먼저 연산이 끝난 녀석이 최소 거리를 가질 수 있음을 

상기해야한다. DFS였다면 모든 경로에 대해 검사를 해야하지만 BFS는 같은 Depth로 퍼져나가기 때문에 

먼저 닿는놈이 최소 거리를 가진다. 이렇게 당연한 개념조차 없었으니 적용할 필요도 없는 조건들에 대해서

생각하느라 풀지못한 것 같다.

 

#BFS를 쓴다면

- 최소 경로

- 배열의 마지막 요소에서의 특정 값 구하기