링크
https://www.acmicpc.net/problem/11403
풀이방법
해당 문제는 BFS를 응용하여 다음과 같은 스텝으로 문제를 해결하였다.
- 우선 양방향 그래프가 아니고 특정 방향으로만 이동할 수 있는 방향 그래프이기 때문에 adj vector 배열 변수에 입력되는 순서로만 값을 대입하였다.
- 문제에서 i에서 간선을 따라 갔을 때 j까지 갈 수 있으면 1을 출력하고 아니면 0을 출력하라고 했으므로 i에서 bfs를 시작해서 이동하다가 j를 만나는 순간 for문과 while문을 탈출하고 출력용 배열인 board에 1을 넣어준다.
- 최종적으로 board 배열을 출력한다.
위 설명의 흐름대로 코드를 보면 무슨 말인지 이해할 수 있을것이다.
코드
#include <bits/stdc++.h>
using namespace std;
int board[105][105];
vector<int> adj[105];
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int num;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> num;
if (num == 1) adj[i].push_back(j);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int vis[105] = {0};
bool flg = false;
queue<int> q;
q.push(i);
while (!q.empty())
{
int cur = q.front();
q.pop();
for (auto nxt : adj[cur])
{
if (nxt == j)
{
board[i][j] = 1;
flg = true;
break;
}
if (vis[nxt]) continue;
q.push(nxt);
vis[nxt] = true;
}
if (flg == true) break;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << board[i][j] << ' ';
}
cout << '\n';
}
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 1991번: 트리 순회 (C++) (0) | 2024.02.02 |
---|---|
백준 11725번: 트리의 부모 찾기 (C++) (0) | 2024.02.02 |
백준 5667번: 결혼식 (C++) (0) | 2024.02.02 |
백준 1260번: DFS와 BFS (C++) (0) | 2024.02.02 |
백준 11724번: 연결 요소의 개수 (0) | 2024.02.02 |