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과 같은 그래프 두 개가..