Algorithm Study Algorithm Study

치즈 문제아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다.다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다.은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은..

핫도그 도난 사건 문제알고리즘 랩스의 사무실에는 긴장감이 감돌고 있습니다. 많던 핫도그가 어느 날 한순간에 없어진 사실에 경악을 금치 못했습니다. 그 사건의 용의자를 찾으려 했으나 쉽지 않았습니다. 이후 이러한 문제가 재발 하지않기 위해 알고리즘 랩스의 직원들은 각 담당 부서별 움직임을 파악할 수 있는 카메라를 만들어 설치를 하는 것이 좋겠다고 합의했습니다. 카메라가 설치되면 직원들의 움직임이 파악되어 냉장고의 음식을 한 사람이 독차지하는 것이 아닌 모두가 즐길 수 있게 될 것이라 믿었습니다. 카메라를 만드는 비용과 시간이 적지않게 들 것으로 예상되어 이를 절감하기 위해 개발팀은 최소한의 카메라로 사무실 인원의 움직임을 파악할 수 있도록 사무실 구조를 파악해야된다고 말했습니다.알고리즘 랩스의 여러 부서는..

비숍(시간제한: 10초) 문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 ..

영역 구하기 문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 M과 N, 그리고 K가 빈칸..

폭발물 설치 문제철수는 마을의 여러 건축물들을 폭파해달라는 요청을 받았다. 이에 건축물들을 하나씩 폭파하려 한다. 일반적으로, 하나의 건물을 폭파하기 위해서는 다이너마이트 하나가 필요하다고 하자. 철수의 마을에 있는 건축물들 사이에는 특별한 단방향 통로가 존재한다. 하나의 건축물을 폭파시킬 경우, 이 단방향 통로로 인하여 상황이 약간 복잡해지는데, 이는 건물 A에서 건물 B로 통로가 이어져 있을 경우, 건물 A를 폭파시키면 건물 B 역시 폭파된다는 것이다. 이유인 즉슨, 단방향 통로가 지하에 매설되어 있기 때문에, 지하의 통로가 무너지면서 건물 B가 함께 무너진다. 철수의 마을에 존재하는 건축물의 개수가 주어지고, 이 건축물들 사이의 단방향 통로가 주어질 때, 최소 몇 개의 다이너마이트가 있어야 모든 건..

SCC 문제SCC (Strongly Connected Component)란, 방향성 그래프가 주어질 때 정점을 여러 집합으로 나누는 기법으로써, 같은 집합에 속해있는 정점끼리는 서로 왔다갔다 할 수 있어야 한다. 아래 그림은 그래프의 예제와, 이 그래프에서 SCC를 구한 예제이다.아래 그림처럼, 정점을 {1, 2, 5}, {6, 7}, {3, 4, 8} 의 3개의 집합으로 나누게 되면, 같은 집합에 속한 정점들끼리는 모두 왔다갔다 할 수 있다. 그래프가 주어질 때, SCC를 구하였을 때 얻을 수 있는 정점의 집합의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어..

파티 문제철수네 마을에는 N개의 집이 있으며, 각 집은 고유한 번호를 부여받는다. 각 번호는 1보다 크거나 같고, N보다 작거나 같다. 철수는 마을 K에 살고 있다. 집과 집 사이에는 단방향 도로가 존재하기 때문에, 이 도로를 통하여 서로 이동할 수 있다. 즉, N개의 마을은 그래프 구조를 이룬다. 편의상 각 집에는 한 사람만이 살고 있다고 가정하자. 크리스마스인 오늘, 철수는 본인의 집에서 파티를 열려고 한다. 따라서 다른 모든 사람들이 철수의 집에 모여 파티를 즐기고, 파티가 끝난 후에는 다시 본인의 집으로 돌아가려 한다. 사람들은 본인의 집에서 철수네 집까지 이동하기 위하여 항상 최단거리로 이동하기를 원하고, 마찬가지로 철수네 집에서 본인의 집에 갈 때도 최단거리로 이동하기를 원한다. 집의 개수와 ..

특정 최단거리 문제그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. 출력1번 정..