4/6 자료구조 B 스터디에서 해결하지 못한 난제

[zs0057]

5214번 환승

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

---

질문

틀린 코드에서 어떤 케이스가 만족하지 않은지 또는 맞은 코드와 차이점이 뭔지 알고 싶습니다.

틀린 코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
vector<int> adj[100000 + 1000 +1];
int dist[100000 + 1000 + 1];
int arr[1001];
int n, k, m;
int bfs(int cur) {
	dist[cur] = 1;
	q.push(cur);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		
		for (auto nxt : adj[cur]) {
			if (dist[nxt] > -1) continue;
			q.push(nxt);
			if (nxt > 100000)
				dist[nxt] = dist[cur];
			else
				dist[nxt] = dist[cur] + 1;
			if (nxt == n) return dist[nxt];  // 맞은 코드와 다른 부분
			
		}
	}
	return -1;
}

int main(void) {
	
	cin >> n >> k >> m;
	int idx = 1;

	while (m--) {
		for (int i = 0; i < k; i++) {
			cin >> arr[i];
		}
		for (int i = 0; i < k; i++) {
			adj[arr[i]].push_back(100000 + idx);
			adj[100000 + idx].push_back(arr[i]);
		}
		idx++;
	}
	fill(dist, dist + 100000 + 1000 + 1, -1);
	cout << bfs(1) << '\n';
	

}

맞은 코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
vector<int> adj[100000 + 1000 +1];
int dist[100000 + 1000 + 1];
int arr[1001];
int n, k, m;
int bfs(int cur) {
	dist[cur] = 1;
	q.push(cur);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		if (cur == n) return dist[cur]; // 틀린 코드와 다른 부분
		for (auto nxt : adj[cur]) {
			if (dist[nxt] > -1) continue;
			q.push(nxt);
			if (nxt > 100000)
				dist[nxt] = dist[cur];
			else
				dist[nxt] = dist[cur] + 1;
			
		}
	}
	return -1;
}

int main(void) {
	
	cin >> n >> k >> m;
	int idx = 1;

	while (m--) {
		for (int i = 0; i < k; i++) {
			cin >> arr[i];
		}
		for (int i = 0; i < k; i++) {
			adj[arr[i]].push_back(100000 + idx);
			adj[100000 + idx].push_back(arr[i]);
		}
		idx++;
	}
	fill(dist, dist + 100000 + 1000 + 1, -1);
	cout << bfs(1) << '\n';
	

}

[joonas-yoon]

@zs0057 N=1 인 케이스(기차역이 하나밖에 없는 경우)에 -1을 출력해서 틀립니다.

input

1 1 1
1

output

1     # answer
-1    # wrong

[zs0057]

답변 감사드립니다.