#1260 DFS와 BFS
DFS & BFS 결과를 한번에 출력할 수 있는 코드를 작성하기 앞서, 나는 DFS, BFS 각각의 코드를 가지고 있었다. 두 코드 모두 독립되어 실행 시에는 문제가 없었다. 따라서 bfs(), dfs() 를 하나의 코드에 통합시키면 되겠다고 생각했다. 그런데 내가 실행해서 테스트했을 때 아웃풋이 완벽하게 나왔다고 생각했음에도 계속 오답판정되었다.
이 때부터 무작정 하나씩 고치며 제출하다보니 며칠이 흘렀고, 디버깅 과정에서 바뀐 코드 각각의 결과를 케이스 별로 기록해놓고 가끔 들여다보기로 했다.🧐
목차
- DFS Code
- BFS Code
- DFS & BFS Code 오답판정 케이스
(1) '틀렸습니다'
(2) '메모리 초과'
(3) '컴파일 에러' - 정답 제출 코드
1. DFS code
처음 내가 가지고 있던 DFS 코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> edge[10001];
bool visit[10001];
int i, j;
void initVisit()
{
for (i = 0; i < 10001; i++)
visit[i] = false;
}
int dfs(unsigned v)
{
visit[v] = true;
printf("%d ", v);
for(i=0; i<edge[v].size(); i++)
if (visit[edge[v][i]] == false) {
dfs(edge[v][i]);
}
return v;
}
void main()
{
unsigned N, M, S; // N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
initVisit();
scanf("%d %d %d", &N, &M, &S);
for (i = 0; i < M; i++)
{
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for (i = 1; i <= N; i++)
sort(edge[i].begin(), edge[i].end());
dfs(S);
}
2. BFS code
BFS 도 DFS code 와 구성은 크게 다르지 않았다.
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
vector<int> edge[10001];
int dist[10001];
int i, j;
void initVisit()
{
for (int i = 0; i < 10001; i++)
{
dist[i] = 100000;
}
}
void bfs(int s)
{
queue<int> q;
int now, k, next;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
now = q.front();
q.pop();
printf("%d ", now);
for (k = 0; k < edge[now].size(); k++) {
next = edge[now][k];
if (dist[next] == 100000) {
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
}
int main()
{
unsigned N, M, S; // N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
initVisit();
scanf_s("%d %d %d", &N, &M, &S);
for (i = 0; i < M; i++)
{
scanf_s("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for (i = 1; i <= N; i++)
sort(edge[i].begin(), edge[i].end());
bfs(S);
}3. DFS & BFS Code 오답판정 케이스
3.(1) '틀렸습니다'
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool visit[1001], edge[1001][1001];
unsigned dist[1001];
unsigned N, M, S;
unsigned i, j;
unsigned dfs(unsigned v)
{
visit[v] = true;
printf("%d ", v);
for (i = 1; i <=N; i++)
if (visit[i] == false && edge[v][i]) {
dfs(i);
}
return v;
}
void bfs(unsigned s)
{
queue<int> q;
unsigned now, k, next;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
now = q.front();
q.pop();
printf("%d ", now);
for (k = 1; k <=N; k++) {
if (dist[k]==10000 && edge[now][k]) {
next = k;
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
}
int main()
{
// N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
scanf("%d %d %d", &N, &M, &S);
//edge = adjacency matrix
for (i = 1; i < M+1; i++)
{
scanf("%d %d", &u, &v);
edge[u][v]=edge[v][u]=true;
}
fill_n(dist, N + 1, 10000);
dfs(S);
printf("\n");
bfs(S);
}3.(2) '메모리 초과'
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<vector<unsigned>> edge;
vector<bool> visit;
vector<unsigned> dist;
unsigned N, M, S;
unsigned i, j;
unsigned dfs(unsigned v)
{
visit[v] = true;
printf("%d ", v);
for (i = 0; i < edge[v].size(); i++)
if (edge[v][i] == 1) {
if (visit[i] == false) {
dfs(i);
}
}
return v;
}
void bfs(unsigned s)
{
queue<int> q;
unsigned now, k, next;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
now = q.front();
q.pop();
printf("%d ", now);
for (k = 0; k < edge[now].size(); k++) {
if (edge[now][k] == 1) {
next = k;
if (dist[next] == 100000) {
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
}
}
int main()
{
// N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
scanf("%d %d %d", &N, &M, &S);
//edge = adjacency matrix
if (1000 < N) N = 1000;
else if (N < 1) N = 1;
else if (10000 < M) M = 10000;
else if (M < 1) M = 1;
edge = vector<vector<unsigned>> (M+1,vector<unsigned>(M+1,0));
visit = vector<bool> (N+1,false);
dist = vector<unsigned> (N+1,100000);
for (i = 1; i < M+1; i++)
{
scanf("%d %d", &u, &v);
edge[u][v]=1;
edge[v][u]=1;
}
dfs(S);
printf("\n");
bfs(S);
}3.(3) 컴파일 에러
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
vector<int> edge[10001];
int dist[10001];
void initVisit()
{
for (int i = 0; i < 10001; i++)
{
dist[i] = 100000;
}
}
void bfs(int s)
{
queue<int> q;
int now, next;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
now = q.front();
q.pop();
printf("%d ", now);
for (int i = 0; i < edge[now].size(); i++) {
next = edge[now][i];
if (dist[next] == 100000) {
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
}
int main()
{
unsigned N, M, S; // N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
initVisit();
scanf_s("%d %d %d", &N, &M, &S);
for (int i = 0; i < M; i++)
{
scanf_s("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for (int i = 1; i <= N; i++)
sort(edge[i].begin(), edge[i].end());
bfs(S);
}4. 정답 제출 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool visit[1001], edge[1001][1001];
unsigned dist[1001];
unsigned N, M, S;
unsigned dfs(unsigned v)
{
visit[v] = true;
cout << v<<" ";
for (int i = 1; i <= N; i++)
if (visit[i] == false && edge[v][i]) {
dfs(i);
}
return v;
}
void bfs(unsigned s)
{
queue<int> q;
unsigned now, next;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
now = q.front();
q.pop();
cout << now << " ";
for (int i = 1; i <= N; i++) {
if (dist[i] == 10000 && edge[now][i]) {
next = i;
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
}
int main()
{
// N: vertices 개수 M:edges 개수 S:시작지점
unsigned u, v;
cin >> N >> M >> S;
//edge = adjacency matrix
for (int i = 1; i < M + 1; i++)
{
cin >> u >> v;
edge[u][v] = edge[v][u] = true;
}
fill_n(dist, N + 1, 10000);
dfs(S);
cout << "\n";
bfs(S);
}
