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. 매칭 문제 N명을 둘씩 짝으로 묶으려고한다. 단 사이가 좋은 사람끼리만 짝을 지어준다고 할때 모든 학생에게 짝을 지어 줄 수 있는지, 불가능하다면 최대 몇 쌍이나 만들 수 있는지 계산하는 문제가 매칭 문제의 예시이다. 이런 문제들은 그래프로 간단하게 표현할 수 있다. 각 사람을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이 때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 한다. 이때 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(maximum matching), 매칭 문제라고 부른다. 매칭 문제는 직관적인 정의를 가진 중요한 문제이다. 하지만 모든 그래프..

1. 문제 N명의 선수를 승부 조작에 참여시켰다. 결승 리그는 여러번의 1:1 경기이다 무승부 없이 항상 승부가 나며 모든 경기가 끝난 후 승수가 가장 많은 선수가 우승한다. 만약 가장 승수가 많은 선수가 둘 이상 있을 겨우 공동 우승을 하게 된다 대부분 우승하지 못할 것으로 여겨지는 X 를 단독 우승하도록해서 이득을 취하려고한다 의심을 피하기위해 가능한 X가 적은 승수로 우승하도록 하고싶다 현재 각 선수의 승수와 남아 있는 경기 목록이 주어질 때. 승부를 적절히 조작해 X가 우승하도록 할 수 있는지 여부를 계산하고, 우승할 수 있다면 필요한 X의 최소 승수는 얼마인지 계산하는 프로그램을 작성하여라. 이때 단독 우승이 불가능할 경우 -1을 출력한다. 그리고 모든 선수가 같은 수의 경기를 치르도록 보장되어..

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

1. 네트워크 모델링 네트워크 유량 문제를 풀 때는 특히나 주어진 문제를 어떻게 그래프로 표현할 것인가가 중요하다. 예제를 통해 그래프를 어떻게 표현할 것인지를 알아보자 2. MILEAGE 마일리지로 여행하기: 자원 분배 신용카드 포인트와 항공사 마일리지 포인트, 이동 통신사 멤버십 포인트 등을 모아서 여행중 쓰려고 한다. 한 종류의 마일리지를 여러 개의 결제 항목에 나눠서 쓸 수 있으며, 한 가지 항목을 여러 개의 마일리지와 현금을 합쳐 결제 하는 것도 가능하다. 단 각 마일리지마다 사용할 수 있는 항목에 제한이 있기 때문에, 어느 마일리지로 무엇을 결제할지 신중해야한다. 결제해야하는 항목들의 가격과 각 마일리지에 쌓인 금액, 각 결제 항목마다 사용할 수 있는 마일리지의 목록이 주어질 때, 사용해야하는..