문제 이해
도시의 수 N, 도로의 수 M, 출발 도시 S, 도착 도시 E가 주어지고 M줄에 걸쳐 연결된 도시들의 번호가 주어진다.
N까지 도시에서 i = 1 to N일 때 i번째 도시를 사용하지 않고 출발 도시에서 도착 도시까지 도착 여부를 구하는 문제.
아이디어 구상
첫번째 시도
벡터를 사용하여 BFS를 돌리면서 방문체크를 하면 될거라 추측했다.
결과 : SUCCESS
두번째 시도
위와 동일하지만 DFS로 돌려봤다.
결과 : FAIL
이유 : 3번째 예제에서 제대로 동작하지 않았다. 혹시 몰라서 벡터들을 정렬시키고 해봤지만 역시나 마찬가지.
조금 더 생각해보고 다시 풀어볼 예정.
코드
#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
#define MX 1005
int vis[MX];
vector<int> v[MX];
int n, m, s, e;
void dfs(int k, int cur) {
for (int i = 0; i < v[cur].size(); i++) {
if (v[cur][i] == k) continue;
if (!vis[v[cur][i]]) {
vis[v[cur][i]] = vis[cur] + 1;
dfs(k, v[cur][i]);
}
}//i
}//dfs
int bfs(int k) {
queue <int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
if (x == e) break;
for (int i = 0; i < v[x].size(); i++) {
if (v[x][i] == k) continue;
if (!vis[v[x][i]]) {
vis[v[x][i]] = vis[x] + 1;
q.push(v[x][i]);
}
}//i
}//w
if (vis[e]) return vis[e];
else return -1;
}//bfs
int main() {
//in
scanf("%d%d%d%d", &n, &m, &s, &e);
for (int i = 0; i < m; i++) {
int u, w;
scanf("%d%d", &u, &w);
v[u].push_back(w);
v[w].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(v[i].begin(), v[i].end());
}
for (int i = 1; i <= n; i++) {
fill(vis, vis + MX, 0);
if (s == i || e == i) printf("-1\n");
else printf("%d\n", bfs(i));
//else {
// vis[s] = 1;
// dfs(i, s);
// printf("%d\n", vis[e] == 0 ? -1 : vis[e]);
//}
}
return 0;
}후기
그래프 탐색을 연습할 수 있는 좋은 기회였다. 문제를 꼼꼼이 읽고 경우의 수를 따져 본 후 푸니 어제보다 잘 풀렸다.
댓글