<div id="readability-page-1" class="page"><div tabindex="-1" id="___gatsby"><header><h2><a href="/">김로그</a></h2><nav><a href="/tags">tags</a>|<a href="/about">about</a></nav></header><main><article><header><time datetime="September 08, 2016">September 08, 2016</time><a rel="tag" href="/tags#플로이드와샬">#플로이드와샬</a> <a rel="tag" href="/tags#floyd-warshall">#floyd-warshall</a> <a rel="tag" href="/tags#백준온라인저지">#백준온라인저지</a> </header><section><a href="https://www.acmicpc.net/problem/11403" target="_blank" rel="noopener">11403번 경로 찾기</a>
가중치 없는 그래프G에서 모든 정점 i, j에 대해서 i에서 j로 가는 경로가 있는지 없는지 구하는 문제이다.
이 문제는 플로이드-워셜 알고리즘 을 사용하면 풀 수 있다. 
i에서 j로 가는 방법은 다음과 같은 방법이 존재한다.
<ul>
<li>i에서 j로 곧장 가는 방법</li>
<li>i에서 임의의 정점 k를 거쳐 j로 가는 방법</li>
</ul>
문제의 입력을 받을 때 i에서 j로 가는길을 입력받기 때문에 i에서 임의의 점점 k를 거쳐 j로 가는 방법들을 추가해주면 된다.
<div data-language="cpp"><pre><code>for(int k = 0 ; k &lt; N ; k++){
 for(int i = 0 ; i &lt; N ; i++){
 for(int j = 0 ; j &lt; N ; j++){
 if( map[i][k] &amp;&amp; map[k][j]){
 map[i][j] = 1;
 }
 }
 }
}</code></pre></div>
전체소스코드
<div data-language="cpp"><pre><code>#include &lt;cstdio&gt;
int N;
int map[100][100]={0,};

int main(){
	int temp;
	scanf("%d",&amp;N);
	for(int i = 0 ; i &lt; N ; i++){
		for(int j = 0 ; j &lt; N ; j++){
			scanf("%d", &amp;map[i][j]);
		}
	}

	for(int k = 0 ; k &lt; N ; k++){
		for(int i = 0 ; i &lt; N ; i++){
			for(int j = 0 ; j &lt; N ; j++){
				if( map[i][k] &amp;&amp; map[k][j]){
					map[i][j] = 1;
				}
			}
		}
	}

	for(int i = 0 ; i &lt; N ; i++){
		for(int j = 0 ; j &lt; N ; j++){
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}

	return 0;
}</code></pre></div>
<hr>
<h2>reference</h2>
<ul>
<li><a href="https://www.acmicpc.net/problem/11403" target="_blank" rel="noopener">11403번 경로 찾기</a></li>
<li><a href="https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98" target="_blank" rel="noopener">플로이드-워셜 알고리즘 - 위키피디아</a></li>
</ul></section><hr></article><nav><ul><li><a rel="prev" href="/beakjoon/2016-09-08-1932/">← 1932번 숫자삼각형</a></li><li><a rel="next" href="/data-structure/2016-09-09-5-bs-tree/">5.Binary Search Tree에 대해서 알아보자. →</a></li></ul></nav></main></div></div>

Kimlog RSS Feed

KIM, WOOJUNG

11403번 경로 찾기
가중치 없는 그래프G에서 모든 정점 i, j에 대해서 i에서 j로 가는 경로가 있는지 없는지 구하는 문제이다.
이 문제는 플로이드-워셜 알고리즘 을 사용하면 풀 수 있다.
i에서 j로 곧장 가는 방법
i에서 임의의 정점 k를 거쳐 j로 가는 방법
문제의 입력을 받을 때 i에서 j로 가는길을 입력받기 때문에 i에서 임의의 점점 k를 거쳐 j로 가는 방법들을 추가해주면 된다.
for(int k = 0 ; k < N ; k++){
 for(int i = 0 ; i < N ; i++){
 for(int j = 0 ; j < N ; j++){
 if( map[i][k] && map[k][j]){
 map[i][j] = 1;
 }
 }
 }
}
전체소스코드
#include <cstdio>
int N;
int map[100][100]={0,};
int main(){
	int temp;
	scanf("%d",&N);
	for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
			scanf("%d", &map[i][j]);
		}
	}
	for(int k = 0 ; k < N ; k++){
		for(int i = 0 ; i < N ; i++){
			for(int j = 0 ; j < N ; j++){
				if( map[i][k] && map[k][j]){
					map[i][j] = 1;
				}
			}
		}
	}
	for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}
reference
11403번 경로 찾기
플로이드-워셜 알고리즘 - 위키피디아

11403번 경로 찾기

댓글