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


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

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2024. 2. 19. 22:37</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/1976" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1976</a></span></h3>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="1053" data-origin-height="233"><span data-url="https://blog.kakaocdn.net/dn/QWud3/btsE0h9TU6e/BhQZeD2XWDgKijuTJXru30/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/QWud3/btsE0h9TU6e/BhQZeD2XWDgKijuTJXru30/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="1053" data-origin-height="233"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 이동하기 원하는 길이 모두 이어져있는지 union find를 통해 간단하게 찾을 수 있다<br>&nbsp;- 각 노드(도시)가 이어진 루트 노드를 별도의 배열에 저장해 둔다.<br>&nbsp;- 이어진 길은 union find로 재귀 탐색하며 루트노드의 값으로 업데이트시킨다<br>&nbsp;- 트리구조에서 스타구조 모형으로 점점 변해가며 시간복잡도가 줄어든다.</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;


std::vector&lt;int&gt; ROAD;


int find(int a) {
	if (a == ROAD[a])
		return a;
	return ROAD[a] = find(ROAD[a]);
}

void UnionFunc(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		ROAD[b] = a;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int city_num, wish_num;

	std::cin &gt;&gt; city_num;
	std::cin &gt;&gt; wish_num;
	std::vector&lt;std::vector&lt;int&gt;&gt; MAP;
	int WISH[1001];

	MAP.resize(city_num+1, std::vector&lt;int&gt;(city_num+1, 0));
	ROAD.resize(city_num + 1);	

	for (int i = 1; i &lt;= city_num; ++i) {
		for (int j = 1; j &lt;= city_num; ++j) {
			std::cin &gt;&gt; MAP[i][j];
		}		
		ROAD[i] = i;
	}

	for (int i = 1; i &lt;= wish_num; ++i) {
		std::cin &gt;&gt; WISH[i];
	}

	for (int i = 1; i &lt;= city_num; ++i) {
		for (int j = 1; j &lt;= city_num; ++j) {
			if (MAP[i][j] == 1) {
				UnionFunc(i, j);
			}
		}
	}

	int index = find(WISH[1]);
	bool connect = true;

	for (int i = 2; i &lt;= wish_num; ++i) {
		if (index != find(WISH[i])) {
			std::cout &lt;&lt; "NO" &lt;&lt; "\n";
			connect = false;
			break;
		}
	}

	if (connect)
		std::cout &lt;&lt; "YES" &lt;&lt; "\n";
	
	return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 오래간만에 푼 코테문제라 union find를 remind 함<br>&nbsp;- union find는 쉬운 개념에다가 구현도 엄청 간단하기에 반드시 알고 있다가 적절할 때 적용해야 한다<br>&nbsp;- 메모리 부족이 처음에 떴는데 vector를 줄이고 array변경하니 해결되었다</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/1976
 
 문제 
 
 
 풀이 
 - 이동하기 원하는 길이 모두 이어져있는지 union find를 통해 간단하게 찾을 수 있다
 - 각 노드(도시)가 이어진 루트 노드를 별도의 배열에 저장해 둔다.
 - 이어진 길은 union find로 재귀 탐색하며 루트노드의 값으로 업데이트시킨다
 - 트리구조에서 스타구조 모형으로 점점 변해가며 시간복잡도가 줄어든다.
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
std::vector<int> ROAD;
int find(int a) {
	if (a == ROAD[a])
		return a;
	return ROAD[a] = find(ROAD[a]);
}
void UnionFunc(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		ROAD[b] = a;
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int city_num, wish_num;
	std::cin >> city_num;
	std::cin >> wish_num;
	std::vector<std::vector<int>> MAP;
	int WISH[1001];
	MAP.resize(city_num+1, std::vector<int>(city_num+1, 0));
	ROAD.resize(city_num + 1);	
	for (int i = 1; i <= city_num; ++i) {
		for (int j = 1; j <= city_num; ++j) {
			std::cin >> MAP[i][j];
		}		
		ROAD[i] = i;
	}
	for (int i = 1; i <= wish_num; ++i) {
		std::cin >> WISH[i];
	}
	for (int i = 1; i <= city_num; ++i) {
		for (int j = 1; j <= city_num; ++j) {
			if (MAP[i][j] == 1) {
				UnionFunc(i, j);
			}
		}
	}
	int index = find(WISH[1]);
	bool connect = true;
	for (int i = 2; i <= wish_num; ++i) {
		if (index != find(WISH[i])) {
			std::cout << "NO" << "\n";
			connect = false;
			break;
		}
	}
	if (connect)
		std::cout << "YES" << "\n";
	
	return 0;
}
 
 알게 된 것 
 - 오래간만에 푼 코테문제라 union find를 remind 함
 - union find는 쉬운 개념에다가 구현도 엄청 간단하기에 반드시 알고 있다가 적절할 때 적용해야 한다
 - 메모리 부족이 처음에 떴는데 vector를 줄이고 array변경하니 해결되었다

Beakjoon] 여행 가자(백준 1976코테) - 그래프 (C++)

댓글