<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:40</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/2178" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/2178</a></span></h3>
<figure id="og_1701696883483" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="2178번: 미로 탐색" data-og-description="첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다." data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2178" data-og-url="https://www.acmicpc.net/problem/2178" data-og-image="https://scrap.kakaocdn.net/dn/8tjsA/hyUIAdsKfN/wFNutSolILKduY9PzHaqwk/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/2178" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/2178">

<div>
<p data-ke-size="size16">2178번: 미로 탐색</p>
<p data-ke-size="size16">첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/8tjsA/hyUIAdsKfN/wFNutSolILKduY9PzHaqwk/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"></figure>

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



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 최단경로를 구하는 문제로 BFS를 사용해서 도달한 깊이값을 사용하면 됨.&nbsp;<br>&nbsp;- 상, 하, 좌, 우 이동이 가능하고 이 이동을 하기위한 값을 미리 저장해 둠.<br>&nbsp;- 방문한 위치는 depth값을 기록하면서 해당 위치에 도달하기 위한 최솟값을 저장해 둠</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;
#include &lt;string&gt;

static std::vector&lt;std::vector&lt;int&gt;&gt; map;
static std::vector&lt;std::vector&lt;bool&gt;&gt; visited;
static int depth=1;
static int dx[] = { 0, 1, 0 ,-1 };
static int dy[] = { 1, 0, -1, 0 };
static int N, M;

void BFS(int x, int y) {
	std::queue&lt;std::pair&lt;int, int&gt;&gt; myQ;
	
	myQ.push(std::make_pair(x, y));
	visited[x][y] = true;

	while (!myQ.empty()) {
		std::pair&lt;int, int&gt; now = myQ.front();
		myQ.pop();
		for (int i = 0; i &lt; 4; ++i) {
			int fir = now.first + dx[i];
			int sec = now.second + dy[i];

			if (fir &gt;= 0 &amp;&amp; sec &gt;= 0 &amp;&amp; fir &lt; N &amp;&amp; sec &lt; M) { //유효성
				if (map[fir][sec] != 0 &amp;&amp; visited[fir][sec] == false) { //방문할 필요가 있는지, 방문이미 했는지
					visited[fir][sec] = true;
					//map[fir][sec]++;
					map[fir][sec] = map[now.first][now.second] + 1;
					myQ.push(std::make_pair(fir, sec));
				}
			}
		}
	}

	
}


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

	std::cin &gt;&gt; N &gt;&gt; M;
	map.resize(N, std::vector&lt;int&gt;(M, 0));
	visited.resize(N, std::vector&lt;bool&gt;(M, false));
	
	for (int i = 0; i &lt; N; ++i) {
		std::string temp;
		std::cin &gt;&gt; temp;
		for (int j = 0; j &lt; M; ++j) {
			map[i][j] = temp[j] - '0';
		}
	}

	BFS(0,0);
	std::cout &lt;&lt; map[N - 1][M - 1];

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

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- <span>최단경로 구하기는 해당 깊이에 대해 전체 탐색을 끝내게 되는 BFS가 적합함</span><br>&nbsp;- 경로가 겹치는 것을 걱정하였으나 이미 최초 해당경로 도달 시 도달 가능한 최솟값이기에 별도의 작업은 필요 없이 방문여부만 체크하면 됨<br>&nbsp;- 상수로 배열의 길이를 선언할 수 있다면 vector를 안 쓰는 게 더 빠르긴 함</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/2178
 
 문제 
 
 
 풀이 
 - 최단경로를 구하는 문제로 BFS를 사용해서 도달한 깊이값을 사용하면 됨. 
 - 상, 하, 좌, 우 이동이 가능하고 이 이동을 하기위한 값을 미리 저장해 둠.
 - 방문한 위치는 depth값을 기록하면서 해당 위치에 도달하기 위한 최솟값을 저장해 둠
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <queue>
#include <string>
static std::vector<std::vector<int>> map;
static std::vector<std::vector<bool>> visited;
static int depth=1;
static int dx[] = { 0, 1, 0 ,-1 };
static int dy[] = { 1, 0, -1, 0 };
static int N, M;
void BFS(int x, int y) {
	std::queue<std::pair<int, int>> myQ;
	
	myQ.push(std::make_pair(x, y));
	visited[x][y] = true;
	while (!myQ.empty()) {
		std::pair<int, int> now = myQ.front();
		myQ.pop();
		for (int i = 0; i < 4; ++i) {
			int fir = now.first + dx[i];
			int sec = now.second + dy[i];
			if (fir >= 0 && sec >= 0 && fir < N && sec < M) { //유효성
				if (map[fir][sec] != 0 && visited[fir][sec] == false) { //방문할 필요가 있는지, 방문이미 했는지
					visited[fir][sec] = true;
					//map[fir][sec]++;
					map[fir][sec] = map[now.first][now.second] + 1;
					myQ.push(std::make_pair(fir, sec));
				}
			}
		}
	}
	
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::cin >> N >> M;
	map.resize(N, std::vector<int>(M, 0));
	visited.resize(N, std::vector<bool>(M, false));
	
	for (int i = 0; i < N; ++i) {
		std::string temp;
		std::cin >> temp;
		for (int j = 0; j < M; ++j) {
			map[i][j] = temp[j] - '0';
		}
	}
	BFS(0,0);
	std::cout << map[N - 1][M - 1];
	return 0;
}
 
 알게 된 것 
 - 최단경로 구하기는 해당 깊이에 대해 전체 탐색을 끝내게 되는 BFS가 적합함
 - 경로가 겹치는 것을 걱정하였으나 이미 최초 해당경로 도달 시 도달 가능한 최솟값이기에 별도의 작업은 필요 없이 방문여부만 체크하면 됨
 - 상수로 배열의 길이를 선언할 수 있다면 vector를 안 쓰는 게 더 빠르긴 함

Beakjoon] 미로 탐색 (백준 2178 코테) - 탐색

댓글