글 읽기 - 1260번 dfs/bfs 문제

dladbwls8 8년 전 0

1260번 dfs/bfs 문제

제 소스가 뭐가 잘못됐는지 모르겠습니다.ㅠㅠㅠ 예제로는 일단 확인했는데 뭔가 중간 테스트케이스에서 문제가 발생한거같아요ㅠㅠ 아무리 생각해봐도 모르겠어서 질문 드립니다.ㅠ

#include <stdio.h>
#include <queue>
using namespace std;

int n;					// 정점 수
int m;					// 간선 수
int start;				// 시작 정점
int Array[1000][1000];	// 인접행렬 저장
int visited[1000];		// i정점을 방문했는지 체크하는 배열
int visit[1000];		// dfs 방문 정점 순서 저장

int visited2[1000];		// i정점을 방문했는지 체크하는 배열
int visit2[1000];		// bfs 방문 정점 순서 저장
int cnt = 0;			// dfs 방문한 정점 카운트
int cnt2 = 0;			// bfs 방문한 정점 카운트
void input()
{
	int x = 0, y = 0;
	scanf("%d%d%d", &n, &m, &start);

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
		Array[x - 1][y - 1] = 1;
		Array[y - 1][x - 1] = 1;
	}
}
void output() {
	for (int i = 0; i < n; i++) {			// dfs 순서 출력
		printf("%d ", visit[i] + 1);
	}
	printf("\n");
	for (int i = 0; i < n; i++) {			// bfs 순서 출력
		printf("%d ", visit2[i]+1);
	}
}
void dfs(int start) {

	visited[start] = 1;						// 출발 정점 방문했다는 것을 표시한다.
	visit[cnt++] = start;					// 방문 정점을 추가한다.	

	for (int i = 0; i < n; i++) {
		if (!visited[i] && Array[start][i] == 1)
		{
			dfs(i);
		}
	}
}
void bfs() {
	queue<int> q;
	int cur = 0;
	q.push(start - 1);						// 출발 정점(인덱스는 0부터이므로 -1해줌)을 큐에 삽입한다.

	while (!q.empty()) {					// 큐가 빌때까지
		cur= q.front();						// 큐 pop하여 현재 정점에 저장
		q.pop();							
		visit2[cnt2++] = cur;				// 현재 정점을 방문 정점에 차례로 저장한다.
		visited2[cur] = 1;					// 현재 정점을 방문 했다고 표시한다.
		for (int i = 0; i < n; i++) {		// 현재 정점으로부터 작은 정점을 우선시하기위해
			if (Array[cur][i] == 1 && !visited2[i])		// 간선으로 연결되어있고 아직 방문하지 않은 정점이면
			{
				q.push(i);					// 큐에 삽입
			}
		}
	}
}
int main()
{
	input();
	dfs(start - 1);
	bfs();
	output();
}

kesakiyo 8년 전 0

bfs할때 큐에서 꺼낼때 visited처리를 하는게 아니라

큐에 넣을 때 visited처리를 해줘야 합니다.

dladbwls8 8년 전 0

그래도 틀렸다고 나오네요...

kesakiyo 8년 전 0

고친 소스를 볼 수 있을까요?

dladbwls8 8년 전 0

여기요ㅠ

#include <stdio.h>
#include <queue>
using namespace std;

int n;					// 정점 수
int m;					// 간선 수
int start;				// 시작 정점
int Array[1000][1000];	// 인접행렬 저장
int visited[1000];		// i정점을 방문했는지 체크하는 배열
int visit[1000];		// dfs 방문 정점 순서 저장

int visited2[1000];		// i정점을 방문했는지 체크하는 배열
int visit2[1000];		// bfs 방문 정점 순서 저장
int cnt = 0;			// dfs 방문한 정점 카운트
int cnt2 = 0;			// bfs 방문한 정점 카운트
void input()
{
	int x = 0, y = 0;
	scanf("%d%d%d", &n, &m, &start);

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
		Array[x - 1][y - 1] = 1;
		Array[y - 1][x - 1] = 1;
	}
}
void output() {
	for (int i = 0; i < n; i++) {			// dfs 순서 출력
		printf("%d ", visit[i] + 1);
	}
	printf("\n");
	for (int i = 0; i < n; i++) {			// bfs 순서 출력
		printf("%d ", visit2[i] + 1);
	}
}
void dfs(int start) {

	visited[start] = 1;						// 출발 정점 방문했다는 것을 표시한다.
	visit[cnt++] = start;					// 방문 정점을 추가한다.	

	for (int i = 0; i < n; i++) {
		if (!visited[i] && Array[start][i] == 1)
		{
			dfs(i);
		}
	}
}
void bfs() {
	queue<int> q;
	int cur = 0;
	q.push(start - 1);						// 출발 정점(인덱스는 0부터이므로 -1해줌)을 큐에 삽입한다.

	while (!q.empty()) {					// 큐가 빌때까지
		cur = q.front();						// 큐 pop하여 현재 정점에 저장
		q.pop();
		visit2[cnt2++] = cur;				// 현재 정점을 방문 정점에 차례로 저장한다.
		
		for (int i = 0; i < n; i++) {		// 현재 정점으로부터 작은 정점을 우선시하기위해
			if (Array[cur][i] == 1 && !visited2[i])		// 간선으로 연결되어있고 아직 방문하지 않은 정점이면
			{
				q.push(i);					// 큐에 삽입
				visited2[i] = 1;					// 현재 정점을 방문 했다고 표시한다.
			}
		}
	}
}
int main()
{
	input();
	dfs(start - 1);
	bfs();
	output();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1260번 dfs/bfs 문제

dladbwls8 8년 전 0

kesakiyo 8년 전 0

dladbwls8 8년 전 0

kesakiyo 8년 전 0

dladbwls8 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말