BaekJoon 11403 경로찾기

 

Link : https://www.acmicpc.net/problem/11403 

소스 결과 : 2064 KB / 12ms

출처 : BackJoon 

 

DFS나 BFS를 사용하는 기초적인 문제라는 느낌이 들었다.

지금 BFS를 공부하는 중이기에 BFS로 문제를 풀었는데 cycle로 처리해서 문제를 해결하는 건가 하는 고민을 처음에 좀 했었다.

결론은 cycle 처리는 bool 배열 하나를 넣는것으로 처리를 마무리 했다.

 

정답은 맞았지만 메모리 2064KB에 12ms 처리 속도

아마 동적배열을 사용하지않고 100개를 미리 만들어두어서 메모리를 좀 많이 잡아먹은 느낌이 있다.

 

소스코드

#include <iostream>

#include <queue>

using namespace std;

int map[100][100];
int moveMap[100][100];

int main()
{
	int caseCount;

	cin >> caseCount;

	for (int i = 0; i < caseCount; i++)
		for (int j = 0; j < caseCount; j++)
			cin >> map[j][i];

	for (int i = 0; i < caseCount; i++)
	{
		queue<int> q;
		bool check[100] = { false , };
		// Start
		q.push(i);

		while (!q.empty())
		{
			// Current Point
			int cLine = q.front();
			q.pop();

			if (check[cLine])
				continue;

			check[cLine] = true;

			// Check Connect Point
			for (int j = 0; j < caseCount; j++)
			{
				if (map[j][cLine] == 1)
				{
					q.push(j);
					moveMap[j][i] = 1;
				}
			}
		}
	}

	for (int i = 0; i < caseCount; i++)
	{
		for (int j = 0; j < caseCount; j++)
			cout << moveMap[j][i] << " ";
		cout << endl;
	}
	

	return 0;
}