[백준] #1260

Hyeju·2022년 11월 8일

#1260 DFS와 BFS

DFS & BFS 결과를 한번에 출력할 수 있는 코드를 작성하기 앞서, 나는 DFS, BFS 각각의 코드를 가지고 있었다. 두 코드 모두 독립되어 실행 시에는 문제가 없었다. 따라서 bfs(), 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);
}

Hyeju

이전 포스트

[백준] #1697 숨바꼭질

다음 포스트

[백준] #1260

#1260 DFS와 BFS

목차

1. DFS code