[백준] 백준 문제 풀이 - 1260 DFS/BFS

2022. 5. 11. 00:10· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어

👩🏻‍💻 문제링크

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

 

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

✍️ 아이디어

1. 문제 이해

  • 처음에 연결리스트로 접근 하려고 했다가 너무 복잡해서 dfs 까지만 구현하고 멈춤
  • 배열로 구현 해서 답이 나왔으나 왠지 모르게 틀림 (왜맞틀?)

2. 내가 생각 못한것은 방문했는지 안했는지 방문일지를 따로 만드는것을 생각하지 못했다!!

-> 난 결과값 저장공간을 따로 만듬

 

3. fill_n(visited, 1001, 0); 를 사용하여 visited의 모든 메모리를 0으로 초기화

✍️소스코드

<나의 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int N,M,V;
    cin >> N >> M >> V; 
	int graph[N+1][N+1]={0};
	for(int i=0; i<M; i++){
        int u,v;
        cin>>u>>v;
        graph[u][v]=1;
        graph[v][u]=1;
    }
    
    //dfs
	vector<int> result1; result1.push_back(V);
	int num=N+1;
	int n=V;
	while(num--)
	{
		for(int m=0; m<N+1; m++)
		{
			if(graph[n][m]==1 && find(result1.begin(), result1.end(), m) == result1.end())
			{
				result1.push_back(m);
				n=m;
				break;
			}
			else
				continue;
		}
	}
	for(auto iter=result1.begin(); iter!=result1.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout<<"\n";
    
    //bfs
	vector<int> result2; result2.push_back(V);
	queue <int> q; q.push(V); num=N+1;
	while(!q.empty())
	{
		n=q.front();
		q.pop();
		for(int m=0; m<N+1; m++)
		{
			if(graph[n][m]==1 && find(result2.begin(), result2.end(), m) == result2.end())
			{
				result2.push_back(m);
				q.push(m);	
			}
		}
	}
	for(auto iter=result2.begin(); iter!=result2.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout<<"\n";
}

 

 

<대다수의 코드> 재귀 DFS

#include<iostream>
#include<queue>


using namespace std;

int line[1001][1001];
int visited[1001]; //방문일지;;
int n, m, v;
queue<int> q;
void dfs(int idx) {
    cout << idx << ' ';

    for (int i = 1; i <= n; i++) {
        if (line[idx][i] && !visited[i])
        {
            visited[i] = 1;
            dfs(i);
        }
    }


}
void bfs(int idx) {

    q.push(idx);

    while (!q.empty()) {

        idx = q.front();

        q.pop();

        cout << idx << ' ';

        for (int i = 1; i <= n; i++) {
            if (line[idx][i] && !visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }


    } 


}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> v;


    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        line[from][to] = 1;
        line[to][from] = 1;
    }
    visited[v] = 1;
    dfs(v);

    cout << '\n';
    fill_n(visited, 1001, 0);
    visited[v] = 1;
    bfs(v);
    return 0;
}

 

<연결리스트 기반의 코드>

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(vector<int>* graph, int start, bool* visited) {
	if (visited[start] != true) {
		visited[start] = true;
		cout << start << ' ';
		for (auto it = graph[start].begin(); it != graph[start].end(); it++) {
			if (visited[*it] != true) {
				dfs(graph, *it, visited);   //함수의 재귀 호출 이용
			}
		}
	}
	else return;
}

void bfs(vector<int>* graph, int start, int n) {
	bool* visited = new bool[n + 1];
	for (int i = 0; i < n + 1; i++) visited[i] = false;

	queue<int> queue;

	visited[start] = true;
	queue.push(start);
	cout << start << ' ';

	if (graph[start].empty()) {  //연결된 간선이 없는 경우 출력 후 바로 리턴
		cout << '\n';
		return;
	}

	while(!queue.empty()) {
		start = queue.front();
		queue.pop();

		if (graph[start].empty()) {  //연결된 간선이 없는 경우 출력 후 바로 리턴
			cout << start << '\n';
			return;
		}

		for (auto it = graph[start].begin(); it != graph[start].end(); it++) {
			if (visited[*it] != true) {
				visited[*it] = true;
				queue.push(*it);
				cout << *it << ' ';
			}
		}
	}

	cout << '\n';
}

int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

	int n, m, start;
	cin >> n >> m >> start;

	int u, v;
	vector<int>* graph = new vector<int>[n + 1];

	for (int i = 0; i < m; i++) {
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	bool* visited = new bool[n + 1];
	for (int i = 0; i < n + 1; i++) visited[i] = false;

	dfs(graph, start, visited);
	cout << '\n';
	bfs(graph, start, n);

	return 0;
}

 

 

체감난이도 걸린시간 참고 사용 문법
중 30min x 벡터, 큐, dfs/bfs

'PS 연습' 카테고리의 다른 글

[PS 풀이] 백준 문제 풀이 - 17298 오큰수  (0) 2022.05.20
[백준] 백준 문제 풀이 - 11724 연결요소의 갯수  (0) 2022.05.11
[PS 연습 - 재귀] 백준 문제 풀이 - 10994 별찍기 - 19  (0) 2022.04.29
[PS 연습 - 정렬] 백준 문제 풀이 - 11651 좌표 정렬하기 2  (0) 2022.04.25
[자료구조] 백준 문제 풀이 - 2075 N번째 큰 수  (0) 2022.04.24
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어
'PS 연습' 카테고리의 다른 글
  • [PS 풀이] 백준 문제 풀이 - 17298 오큰수
  • [백준] 백준 문제 풀이 - 11724 연결요소의 갯수
  • [PS 연습 - 재귀] 백준 문제 풀이 - 10994 별찍기 - 19
  • [PS 연습 - 정렬] 백준 문제 풀이 - 11651 좌표 정렬하기 2
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 원형 연결 리스트
  • sentry
  • 양방향 연결 리스트
  • 재귀
  • dp
  • 수식트리
  • 파일 업로드
  • CPP
  • DN
  • open api
  • Stream
  • 백준 골드
  • 이진트리
  • aws rds
  • 자료구조
  • 브루트 포스
  • 배열 리스트
  • 단순 연결 리스트
  • 예외처리
  • 스택
  • 알고리즘
  • 완전탐색
  • ㄱ
  • 열혈 자료구조
  • backend
  • 해커톤
  • 트리
  • 큐
  • 스프링
  • 백준

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[백준] 백준 문제 풀이 - 1260 DFS/BFS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.