boj 11403 - 경로 찾기 (골드 티어 관문 입장)

해당 문제는 solved.ac 티어 골드 5관문을 입장하게 한 문제로 

기념비적으로 정리해 본다.

문제이름

boj 11403 경로 찾기

 

문제 설계

• 방향 그래프
• i에서 j로 갈 수 있는 경로 존재 여부 출력
• 최단거리 X
• 단순 도달 가능성 문제

생각한 문제 패턴

• (i, j) 쌍에 대해 BFS를 개별적으로 돌려야 한다고 생각
• 2차원 visited로 관리하려고 함
• (start, end)를 큐에 pair로 넣는 방식으로 전이 폐쇄 구현 시도
• visited를 전역으로 유지해야 하나 고민

-> 한 쌍씩 확인해야 한다는 사고로 접근

 

알고리즘 1 (초기 잘못된 접근)

• bfs(adj, visited, start, end)
• (start, end) 쌍을 상태로 관리
• visited를 2차원으로 두고 전이 확장

문제점

• BFS가 불필요하게 복잡해짐
• adj 대신 visited를 간선처럼 사용하려는 오류
• 쌍 상태는 전통 BFS 구조와 맞지 않음

잘못됨 판단 신호

• BFS를 j마다 호출하려 함
• visited를 전역으로 유지해야 하나 고민
• 2차원 visited로 전이 관계를 직접 관리하려 함
• ans 복사 로직이 3중 루프 형태로 복잡해짐

-> 문제를 “행 단위 도달 집합”으로 보지 못함

 

해결 방법 

adj 배열에서 i 노드 j노드 관계

i노드에서 1~n번째로 갈수 있는지 판단을

1~n번 수행

 

추가 탐구 부분

• 플로이드 와샬 알고리즘 탐구

void bfs(vector<vector<int>> &adj, vector<bool> &visited, vector<vector<bool>> &ans, int x)
{
	queue<int> q;
	q.push(x);
	
	int n = visited.size()-1;

	while(!q.empty())
	{
		int cur = q.front();
		q.pop();

		for(int i=1; i<=n; i++)
		{
			if( visited[i] == false && adj[cur][i] ==1 )
			{
				visited[i] = true;
				q.push(i);
			}
		}
	}

	for(int i=1; i<=n ;i++)
	{
		ans[x][i] = visited[i];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin>>n;

	vector<vector<int>> adj(n+1, vector<int>(n+1,0));
	vector<bool> visited (n+1, false);

	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cin>>adj[i][j];
		}
	}

	vector<vector<bool>> ans(n+1,vector<bool>(n+1,0));

	for(int i=1; i<=n; i++)
	{	
		visited.assign(n+1,false);
		bfs(adj, visited, ans, i);
	}

	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cout<<ans[i][j]<<" ";
		}
		cout<<"\n";
	}

}