https://www.acmicpc.net/problem/11403 [ 나의 해결법 ]노드 1을 시작점으로 깊이우선탐색을 한다. 이 때 방문한 노드는 노드1에서 갈 수 있는 노드이므로 인접행렬(배열 adj)에 표시해둔다.시작점을 노드1부터 노드 N까지 반복한다. 그럼 모든 정점에 대해서 경로의 존재여부를 구할 수 있다.문제는 깊이우선탐색(DFS)를 이용했다. DFS를 재귀로 많이 구현하는데, 재귀로 구현했다가 시간 초과가 나서 스택(Stack)으로 구현했다. 어차피 재귀도 스택이므로 방법이 크게 다른건 아니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859..
https://www.acmicpc.net/problem/1389 [ 나의 해결법 ]다익스트라 알고리즘을 이용해서 문제를 풀었다. 사람1을 시작해서 다익스트라 알고리즘을 진행하면, 사람1과 다른 사람들과의 최단거리를 배열 dist에 구할 수 있다. 배열 dist의 모든 원소를 더하면 사람1의 케빈 베이컨의 값이 나온다.이런 식으로 사람1부터 N명까지 진행하면서 케빈 베이컨 값이 최소의 유저를 찾으면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #..
https://www.acmicpc.net/problem/1707 [ 그림1. 이분 그래프 설명 ][ 나의 해결법 ]그림1처럼 각 집합(파랑색과 빨강색)안에 노드들끼리 간선이 없으면 이분그래프가 된다. 그럼 어떻게 이분그래프인지 알 수 있을까? 주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다. [ 출처 : 위키백과 ] 이 문제에서 주의해야할 점은 다른 노드들과는 아예 분리된 노드가 존재할 수 있다는 것이다. 그림1과 같은 그래프 두 개가..
https://www.acmicpc.net/problem/1238 [ 나의 해결법 ]이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 그런데 그냥 다익스트라 알고리즘으로 풀면 시간초과가 난다. 시간복잡도를 계산하면 10억이 훌쩍 넘는다. 3중 for문을 돌기 때문이다.다른 사람들의 질문들을 보니 플로이드 와샬 알고리즘을 이용한 사람도 있다. 그런데 나는 우선순위 큐를 이용한 알고리즘을 사용할 것이다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #in..
다익스트라 알고리즘에 대해 자세히 설명된 곳을 추천한다.http://www.playsw.or.kr/repo/cast/105 우선 위 주소로 가서 다익스트라 알고리즘이 어떻게 동작하는지 한번 살펴보길 추천한다. 단계별로 설명되어 있기 때문이 차근 차근 읽어보면 쉽게 이해할 수 있다. 내가 이해한 다익스트라 알고리즘은 출발지로부터 갈 수 있는 노드의 최단 거리를 모든 노드를 방문할 때까지 계속 갱하는 방법이다. 1. 먼저, 집에서 갈 수 있는 곳을 그림의 표에서 거리 칸에 써 넣는다. 2. 그리고 집에서 갈 수 있는 곳은 미용실, 슈퍼마켓, 영어학원 중에서 최단거리인 미용실로 간다. 3.다시 미용실에서 갈 수 있는 곳은 슈퍼마켓, 은행이다.(집은 이미 방문했으니 패스~)여기서 슈퍼마켓으로 가는 경로는 집에서..