<div id="readability-page-1" class="page">
                
                
                


<div id="wrap">
	
	<hr>
	<section>
		
		<article id="content">
			

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 4. 22:34</span>
				
			</p>
		</div>
		<div><hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<h3 data-ke-size="size23"><br>🅰️문제주소 :<span> <a href="https://www.acmicpc.net/problem/1260" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1260</a></span></h3>
<figure id="og_1701696567880" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1260번: DFS와 BFS" data-og-description="첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1260" data-og-url="https://www.acmicpc.net/problem/1260" data-og-image="https://scrap.kakaocdn.net/dn/blL7mm/hyUIvwrGgM/r8D1NWRlCTppAO6O0k4Rdk/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/1260" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/1260">

<div>
<p data-ke-size="size16">1260번: DFS와 BFS</p>
<p data-ke-size="size16">첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/blL7mm/hyUIvwrGgM/r8D1NWRlCTppAO6O0k4Rdk/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"></figure>

<h3 data-ke-size="size23">🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="995" data-origin-height="182"><span data-url="https://blog.kakaocdn.net/dn/y9kdC/btsBldC9XVo/uKEkaetxeYlfZhynlmPMMK/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/y9kdC/btsBldC9XVo/uKEkaetxeYlfZhynlmPMMK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="995" data-origin-height="182"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- DFS와 BFS의 기본적인 구현. 탐색이 끊긴다던가 특정 depth의 값을 구하는 것이 아니므로 특별한 조건 없이 구현하면 된다.&nbsp;<br>주의할 점은 방문할 수 있는 정점이 여러개면 번호가 작은 것부터 방문하게 해야 한다는 것인데 이는 정렬을 통해 다른 조건을 줄 필요 없이 간단하게 해결된다.</p>

<h3 data-ke-size="size23">☕코드는 아래 숨김</h3>
<div data-text-less="닫기" data-text-more="더보기" data-ke-type="moreLess"><p><a>더보기</a></p><div>
<pre id="code_1701091944942" data-ke-language="cpp" data-ke-type="codeblock"><code>#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
#include &lt;queue&gt;
#include &lt;algorithm&gt;

std::vector&lt;bool&gt; visited;
std::vector&lt;std::vector&lt;int&gt;&gt; map;

std::string result;
int N, M;

void DFS(int num) {
    std::cout &lt;&lt; num &lt;&lt; " ";
    visited[num] = true;

    for (int i = 0; i &lt; map[num].size(); ++i) {
        if (visited[map[num][i]] == false)
            DFS(map[num][i]);
    }    
    return;
}

void BFS(int num) {
    std::queue&lt;int&gt; myQ;    
    myQ.push(num);
    visited[num] = true;

    while (!myQ.empty()) {
        int now_node = myQ.front();
        myQ.pop();
        std::cout &lt;&lt; now_node &lt;&lt; ' ';
        for (int i : map[now_node]) {
            if (visited[i] == false) {
                visited[i] = true;
                myQ.push(i);
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    int V;
    std::cin &gt;&gt; N &gt;&gt; M &gt;&gt; V;

    visited.resize(N+1, false);
    map.resize(N+1);

    int f, b;
    for (int i = 1; i &lt;= M; ++i) {        
        std::cin &gt;&gt; f &gt;&gt; b;
        map[f].push_back(b);
        map[b].push_back(f);
    }
    for (int i = 1; i &lt;= N; ++i) {
        std::sort(map[i].begin(), map[i].end());
    }
    
    DFS(V);
    std::cout &lt;&lt; "\n";
    result = "";
    visited.resize(0);
    visited.resize(N+1, false);

    BFS(V);

}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- BFS에 대해 이론적으로만 알고 있었으나 실제 C++에서 Queue를 사용하여 구현해봄.<br>- 이차원벡터의 sort 사용해 봄</p>
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
</div>
		

		
			<div>
				<h2><strong>'운동하는 개발자/알고리즘, 코딩테스트'</strong> Related Articles</h2>
				
			</div>
		

		



	

                
            
			</div>

			

			

			

		</article>
	</section>
	<hr>
	
	
</div>







                




        
        











  


        

                
                







                
                


                

</div>

운동하는 개발자

️문제주소 : https://www.acmicpc.net/problem/1260
 
 문제 
 
 
 풀이 
 - DFS와 BFS의 기본적인 구현. 탐색이 끊긴다던가 특정 depth의 값을 구하는 것이 아니므로 특별한 조건 없이 구현하면 된다. 
주의할 점은 방문할 수 있는 정점이 여러개면 번호가 작은 것부터 방문하게 해야 한다는 것인데 이는 정렬을 통해 다른 조건을 줄 필요 없이 간단하게 해결된다.
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
std::vector<bool> visited;
std::vector<std::vector<int>> map;
std::string result;
int N, M;
void DFS(int num) {
    std::cout << num << " ";
    visited[num] = true;
    for (int i = 0; i < map[num].size(); ++i) {
        if (visited[map[num][i]] == false)
            DFS(map[num][i]);
    }    
    return;
}
void BFS(int num) {
    std::queue<int> myQ;    
    myQ.push(num);
    visited[num] = true;
    while (!myQ.empty()) {
        int now_node = myQ.front();
        myQ.pop();
        std::cout << now_node << ' ';
        for (int i : map[now_node]) {
            if (visited[i] == false) {
                visited[i] = true;
                myQ.push(i);
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    int V;
    std::cin >> N >> M >> V;
    visited.resize(N+1, false);
    map.resize(N+1);
    int f, b;
    for (int i = 1; i <= M; ++i) {        
        std::cin >> f >> b;
        map[f].push_back(b);
        map[b].push_back(f);
    }
    for (int i = 1; i <= N; ++i) {
        std::sort(map[i].begin(), map[i].end());
    }
    
    DFS(V);
    std::cout << "\n";
    result = "";
    visited.resize(0);
    visited.resize(N+1, false);
    BFS(V);
}
 
 알게 된 것 
 - BFS에 대해 이론적으로만 알고 있었으나 실제 C++에서 Queue를 사용하여 구현해봄.
- 이차원벡터의 sort 사용해 봄

Beakjoon] DFS와 BFS (백준 1260 코테) - 탐색

댓글