(백준/c++) 14940 - 쉬운 최단 거리 / DFS, 그래프

 

" (백준/c++) 14940 - 쉬운 최단 거리 / DFS, 그래프 "

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

 

🏆 solved.ac 난이도: 실버1

이 문제는 쉽게 풀어서 solved.ac에 검색해봤는데 실버 1 문제당.. 힝 !!! 

내 실력은 아직 골드5, 실버1 정도 되는거 같다 ㅠㅁㅠ 

넓이 우선 문제로 시작점부터 찬찬히 넓혀가면 되는 문제다. 

항상 BFS문제에서 실수하는 부분을 다시 짚고 넘어가려고 작성한다. 

 

que에 조건이 되는 노드를 push 할 때 방문처리를 해주는거다. 

pop 하면서 방문처리하니깐 괜찮지 않나? 생각하면서 항상 빼곤 한다.

그렇게 되면 아래와 같이 E가 que에서 pop되고 방문처리하기 전에 D에서 'visit false군!!" 하면서 que에 넣으면서 무한루프에 빠져버린다. 

 

조건되는 노드를 visit해주지 않을 경우

#include<iostream>
#include<queue>
#include<array>
using namespace std; 

int ArrMap[1001][1001] = { 0, };
int ArrResult[1001][1001] = { 0, };
bool visit[1001][1001] = { false };

pair<int, int> direction[4] = {{ -1, 0}, {1, 0}, { 0, -1}, {0, 1} };

int main(void)
{
	int N, M; 
	cin >> N >> M;
	pair<int, int> targetPoint;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> ArrMap[i][j]; 
			if (ArrMap[i][j] == 2)
			{
				targetPoint.first = i; 
				targetPoint.second = j;
			}
		}
	}

	queue<pair<int, int>>  que; 
	que.push(make_pair(targetPoint.first, targetPoint.second));
	ArrResult[targetPoint.first][targetPoint.second] = 0;

	while (!que.empty())
	{
		auto temp  = que.front();
		visit[temp.first][temp.second] = true; 
		que.pop();

		for (int i = 0; i < 4; ++i)
		{
			int X = temp.first + direction[i].first; 
			int Y = temp.second + direction[i].second; 

			if (ArrMap[X][Y] == 0)
			{
				continue;
			}
			else if (X >= 0 && X < N && Y >= 0 && Y <M && visit[X][Y] == false)
			{
				ArrResult[X][Y] = ArrResult[temp.first][temp.second] + 1; 
				visit[X][Y] = true;
				que.push(make_pair(X, Y));
			}

		}
	}


	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (i == targetPoint.first && j == targetPoint.second)
			{
				cout << 0 << " ";
			}
			else if (ArrResult[i][j] == 0 && ArrMap[i][j] != 0 )
			{
				cout << -1 << " ";
			}
			else
			{
				cout << ArrResult[i][j] << " ";
			}
		}
		cout << endl;
	}

	return 0; 
}