1. 문제 타일이 주어지면 '.'에 함정을 설치한다고 한다. 이때 함정은 상하좌우 4칸에 다른 함정이 없어야된다. 이때 최대 함정을 설치할 수 있는 갯수와 함정의 위치를 포함한 타일을 출력해야한다. 2. 암시적 그래프 타일을 상하좌우를 간선으로 가지는 암시적인 그래프로 표현할 수 있다. 이를 이용해 이분 그래프의 매칭 문제의 dfs코드를 조금 변형하면 최대한 많은 타일에 함정을 매칭할 수 있다. 이분 그래프로 생각하면 다음과 같다. a그룹 = '#' 이 아닌 타일 전체 b그룹 = 상하좌우중간 으로 묶여진 타일들의 집합. 중간을 기준으로 구별할 수 있다. 3. 이분 그래프의 매칭 dfs 모든 타일을 조사하면서 '.' 인 타일에대해 dfs를 실행한다. (a그룹을 하나씩 조사) 주위에 함정이 없어 함정을 설치..

1. 문제 게임판과 장애물의 위치가 주어진다. 이 게임판 위에서 비숍을 서로 죽일수 없도록 최대한 몇개 배열할 수 있는지 계산하는 문제이다. 2. 이분 매칭 비숍은 대각선으로만 이동할 수 있다. 오른쪽으로 가는 대각선과 왼쪽으로 가는 대각선 두개로 비숍의 위치를 나타낼 수 있다. 그러므로 해당 대각선에 비숍이 두개 있을 경우 서로 죽일 수 있다. 이를 이용하여 오른쪽 대각선과 왼쪽대각선을 a그룹 b그룹으로 나누어 이분 할 수 있으며 최대한 많이 비숍을 배열해야하므로 이는 이분 최대 매칭 문제가 된다. 따라서 그래프만 적절히 표현하면 문제는 쉽게 해결된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..

1. 문제 A나라와 B나라가 경기를 한다고 한다. 이때 종목들과 종목마다 두 나라 선수의 예상 기록이 주어질때 두 나라를 무승부로 만들려고한다. 이때 가장 짧은 기록을 구하는 문제이다. 만약 무승부가 될 수 없으면 IMPOSSIBLE을 출력한다. 2. 책의 풀이: 그래프의 생성 만들수 있는 코스는 무한히 많다. 따라서 완전 탐색으로 이 문제를 풀기 불가능하지만 모든 코스를 다 만들어 봐야하는 것은 아니다. 힌트는 종목들 간의 순서가 상관이 없다는 것이다. 이 문제에서 종목들의 종류나 순서는 중요하지 않다. 의미 있는 것은 두 선수의 예상 시간 차이 뿐이다. 코스에 종목을 하나 추가하면, 그 종목에 따라 차이는 변화한다. 이와 같은 정보를 그래프로 표현하려면 A국 선수의 예상 시간에서 B국 선수의 예상 시..

1. 문제 한 도시에서 다른 도시까지 여행을 하고싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 운행 속도가 정해져 있다. 가속과 감속을 반복하면 멀미때문에 괴롭다. 따라서 항상 비슷한 속도로 여행하고싶다. 철도망이 주어질때 여행 구간 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 프로그램을 작성하라 시작 철도역은 항상 0 번이고 도착할 철도역은 항상 N-1번이다. 2. 책의 풀이1 어떤 경로에서 모든 간선의 가중치가 어떤 값 U이거나 그보다 작을 때, U를 '상한'이라고 하고 반대로 모든 간선의 가중치가 어떤 값 L이거나 그보다 클 때, L을 이 경로의 '하한'이라고 하자. 경로의 최소 상한과 최대 하한의 차이를 경로의 '너비'라고 하면 ..

1. 문제 이 문제는 이미 연결된 집합을 한 정점으로 표현하여 최소 스패닝 트리를 구하는 문제이다. 이 문제의 핵심은 연결된 집합을 한 정점으로 어떻게 표현할 것인가에 있다. 2. 유니온 파인드 : 크루스칼 알고리즘 이미 연결된 집합을 유니온-파인드 자료구조로 표현하여 각 집합사이의 최소 거리를 구하려면 많이 복잡하다. 이를 간결하게 구현하려면 소방차 문제에서 그랬듯이 임의적인 방법이 필요하다. 그러므로 책에서는 연결된 정점끼리 이어지는 간선의 가중치를 0으로 설정해서 항상 이 간선을 선택하게끔 하였고 가중치가 0이므로 추가되는 가중치의 합을 구할 수 있게 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

1. 최소 스패닝 트리(Minimum Spanning Tree) 외판원 문제 휴리스틱에서나 각종 그래프의 탐색 알고리즘, 최단 경로 알고리즘에서 경로를 찾는데에 사용했었다. 어떤 무향 그래프의 스패닝 트리(Spanning Tree)는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. 트리 형태라는 것은 선택된 간선들이 사이클을 이루지 않는다는 것을 의미하며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 것을 의미한다. 또한 그래프안에 여러 개의 스패닝 트리가 있다. 이런 스패닝 트리 중에서 가중치의 그래프의 스패닝 트리 중 가중치 합이 가장 작은 트리를 찾는 문제를 최소 스패닝 트리 문제(Minim..