1. 문제 모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다. 이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.) 어떤 방에 카메라를 설치했다고 하자. 그러면 그 방 주위의 방들을 감시할 수 있다. 1칸밖에 감시를 못하므로 이것은 '리프' 에서부터 차근 차근 카메라를 설치해야한다. '리프' 에서부터 탐색하는하는 것은 dfs를 이용하면 쉽게 구현할 수 있다. 2. dfs 일단 루트에서부터 dfs를 실행하게 되면 제일먼저 종료되는 dfs는 '리프'이다. '리프' 이전의 방에서는 무조건 카메라가 설치되어야 '리프'를 감시 할 수 있다. 그러므로 '리프' 이전의 방에 카메라를 설치한다. 이 문제에서 '리프'는 연결점이 타고내려온 것을 제외하고는 아무것도 없는 정점을..

1. 간선의 분류: 유향 dfs를 수행하면 그래프의 간선을 한 번씩은 조사하게 된다. 간선의 종류는 두가지가 있다. - 처음 발견된 정점으로 연결된 간선 - 무시되는 간선 이들에 대한 정보를 수집하면 그래프 구조에 대해 많은 것을 알 수 있다. 일단 연결된 간선들만을 모아보면 트리 형태를 띠게 된다. (위 그림은 0번 정점을 루트로 하는 트리 형태) 이 트리의 이름을 그래프의 깊이 우선 탐색의 스패닝 트리 혹은 DFS 스패닝 트리 라고 부른다. DFS스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다. - 트리 간선(tree edge) : 스패닝 트리에 포함된 간선 - 순방향 간선(forward edge) : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 말한다. 위 ..

1. 문제 끝말잇기 참가자 = 원으로 앉아있음 시계방향으로 단어를 말함 단어의 첫글자 = 이전사람이 말한 글자의 끝 단어의 종류가 정해짐 한단어 두번X 단어들을 전부 사용가능한지 판단하고 어떤 순서로 단어를 사용해야하는지를 계산하는 문제 2. 오일러 트레일 이 문제는 각 단어의 첫부분과 끝부분으로 만들어진 간선을 가지는 그래프를 만들고 오일러 트레일과 오일러 경로 구하는 문제인것 같다. 하지만 책에서 구현한 오일러 경로를 아직 이해하지 못하겠다. 간선이 아닌 정점을 벡터에 집어넣는것, 아직 생각을 더해야 겠다. 또한 그래프를 생성하고 홀수점이 2개일때 오일러 트레일을 찾을려면 홀수점 두개중에서 시작점과 끝점을 찾아야하는게 문제이다. (책의 풀이를 보고, 방향그래프인점을 생각하지 못한 것을 알게되었다.) ..

1. 오일러 서킷 (Eulerian circuit) - 한붓 그리기 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제 이와 같은 경로를 그래프 이론에서 오일러 서킷이라고 부른다. 오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우를 생각하는것이다. 가장 생각하기 쉬운 경우는 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우이다. (간선을 가지지 않은 컴포넌트는 예외) 정점의 차수(degree) 시작점이 u이고 끝점이 v인 특정 경로 u->v 가 모든 간선을 지나지 못하고 끝났다고 해보자. 이는 v에서 연결된 간선은 전부 한번 씩 지나갔다는 것을 의미한다. (갈곳이 없다) u != v: 항상 v는 홀수 개의 간..

1. 문제 고대어 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있지만, 사전에 포함된 단어의 순서들이 영어와 서로 다르다. 사전선이 다른 순서인지 알파벳 순서가 영어와 서로 다른 것인지 알기 위해 사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하여라 2. DFS, 위상정렬, DAG - 사이클이 없는 방향그래프일때 해당 순서를 계산할 수 있을 것이다. - DAG를 다루는 문제로 각 알파벳을 정점으로하고 다음문자와의 비교를 통해 알파벳끼리의 간선을 생성할 수 있을 것이다. 이 문제는 사이클만 찾는 코드를 구현하면 쉽게 풀 수 있다. 사이클이 생기는 경우는 한가지만 체크하면된다. 위상정렬을 구하기 위해 dfs를 실행하는 중 함수가 종료될..

1. 그래프 탐색 (search) 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색이라고 한다 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 2. 깊이 우선 탐색 (Depth-first search, DFS) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 이다. 따라갈 간선이 없으면 마지막에 따라왔던 간선을 따라 뒤 돌아간다. 위 그림들은 정점의 번호가 작은것을 먼저 탐색하는 dfs의 예시이다. 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 ..