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


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

			

			

			

			<div>
				

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

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="1082" data-origin-height="361"><span data-url="https://blog.kakaocdn.net/dn/UYtFH/btsDnCIfaBe/28AumbdtJOXcsKq3wK0Lsk/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/UYtFH/btsDnCIfaBe/28AumbdtJOXcsKq3wK0Lsk/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="1082" data-origin-height="361"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 그래프로 map을 그려놓고 BFS, DFS 하는 것이 아닌 역으로 그래프를 그리는 문제<br>&nbsp;- 2차원 길찾기와 유사하게 물의 이동의 케이스를 배열로 구성한다. (0-&gt;1, 0-&gt;2, 1-&gt;0, 1-&gt;2, 2-&gt;0, 2-&gt;1)<br>&nbsp;- 방문여부는 A와 B의 물통 양으로 이차원 배열을 만들어서 체크한다.<br>&nbsp;- A, B, C의 물통의 양을 입력받은 뒤 BFS탐색을 시작하되 이동할 노드를 큐에 추가하고(예:0에서 1)<br>방문한 경우는 제외시킨다.<br>&nbsp;- 받는물통한테 보내는 물통의 모든 용량을 추가한 뒤 기존 물통의 크기를 초과한 경우 초과한 만큼 다시 보내는 물통으로 보낸다. 초과하지 않았을 경우 보내는 물통은 0을 저장한다.<br>&nbsp;- 이 과정 후 A의 물통이 0이면 C물통의 용량을 정답 배열에 true로 변경한다</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;queue&gt;

bool answer[201];
int now[3];
int sender[] = { 0, 0, 1, 1, 2, 2 };
int reciver[] = { 1, 2, 0, 2, 0, 1 };
bool visited[201][201];


void BFS() {
	std::queue&lt;std::pair&lt;int, int&gt;&gt; q;
	q.push(std::make_pair(0, 0));
	visited[0][0] = true;
	answer[now[2]] = true;

	while (!q.empty()) {
		int A = q.front().first;
		int B = q.front().second;
		q.pop();
		int C = now[2] - A - B;

		for (int i = 0; i &lt; 6; ++i) {
			int next[] = { A,B,C };
			next[reciver[i]] += next[sender[i]];
			next[sender[i]] = 0;

			if (next[reciver[i]] &gt; now[reciver[i]]) {
				next[sender[i]] = next[reciver[i]] - now[reciver[i]];
				next[reciver[i]] = now[reciver[i]];
			}
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(std::make_pair(next[0], next[1]));
				if (next[0] == 0) {
					answer[next[2]] = true;
				}
			}
		}
	}
}

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

	std::cin &gt;&gt; now[0] &gt;&gt; now[1] &gt;&gt; now[2];
	BFS();

	for (int i = 0; i &lt; 201; ++i) {
		if (answer[i])
			std::cout &lt;&lt; i &lt;&lt; " ";
	}

	
	return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 제법 어려웠던 문제. 수도코드를 보고도 감을 잡기 어려웠다.<br>&nbsp;- 이차원 지도에서 빠른 길 찾기 같은 것을 풀 때 쓰던 좌표값 같은 것을 물의 이동으로 그려서 표현하는 것<br>&nbsp;- 어렵다 어려워</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/2251
 
 문제 
 
 
 풀이 
 - 그래프로 map을 그려놓고 BFS, DFS 하는 것이 아닌 역으로 그래프를 그리는 문제
 - 2차원 길찾기와 유사하게 물의 이동의 케이스를 배열로 구성한다. (0->1, 0->2, 1->0, 1->2, 2->0, 2->1)
 - 방문여부는 A와 B의 물통 양으로 이차원 배열을 만들어서 체크한다.
 - A, B, C의 물통의 양을 입력받은 뒤 BFS탐색을 시작하되 이동할 노드를 큐에 추가하고(예:0에서 1)
방문한 경우는 제외시킨다.
 - 받는물통한테 보내는 물통의 모든 용량을 추가한 뒤 기존 물통의 크기를 초과한 경우 초과한 만큼 다시 보내는 물통으로 보낸다. 초과하지 않았을 경우 보내는 물통은 0을 저장한다.
 - 이 과정 후 A의 물통이 0이면 C물통의 용량을 정답 배열에 true로 변경한다
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <queue>
bool answer[201];
int now[3];
int sender[] = { 0, 0, 1, 1, 2, 2 };
int reciver[] = { 1, 2, 0, 2, 0, 1 };
bool visited[201][201];
void BFS() {
	std::queue<std::pair<int, int>> q;
	q.push(std::make_pair(0, 0));
	visited[0][0] = true;
	answer[now[2]] = true;
	while (!q.empty()) {
		int A = q.front().first;
		int B = q.front().second;
		q.pop();
		int C = now[2] - A - B;
		for (int i = 0; i < 6; ++i) {
			int next[] = { A,B,C };
			next[reciver[i]] += next[sender[i]];
			next[sender[i]] = 0;
			if (next[reciver[i]] > now[reciver[i]]) {
				next[sender[i]] = next[reciver[i]] - now[reciver[i]];
				next[reciver[i]] = now[reciver[i]];
			}
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(std::make_pair(next[0], next[1]));
				if (next[0] == 0) {
					answer[next[2]] = true;
				}
			}
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	std::cin >> now[0] >> now[1] >> now[2];
	BFS();
	for (int i = 0; i < 201; ++i) {
		if (answer[i])
			std::cout << i << " ";
	}
	
	return 0;
}
 
 알게 된 것 
 - 제법 어려웠던 문제. 수도코드를 보고도 감을 잡기 어려웠다.
 - 이차원 지도에서 빠른 길 찾기 같은 것을 풀 때 쓰던 좌표값 같은 것을 물의 이동으로 그려서 표현하는 것
 - 어렵다 어려워

Beakjoon] 물통 (백준 2251코테) - 그래프 (C++)

댓글