회로 배치 |
---|
회로는 \(n \times n \)의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)은 가장 자리에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이숫 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다. 아래 그림에서는 X와 Y, P와 Q를 연결한 두 개의 회로가 있다. 이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때, 이들 두 격자를 잇는 새로운 회로를 배치하려고 하다. 새로 배치될 회로는 이미 회로가 배치된 격자 위에 배치될 수도 있다. 이 회로의 배치 비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다. 회로가 배치되지 않은 빈 격자를 지나는 비용은 1이고, 이미 회로가 놓여 있는 격자를 지날 때는 비용이 \(k(k\geq2) \)이다. 주어진 문제는 최소의 비용이 소요되는 새로운 회로를 찾는 것이다. 예를 들어, 아래의 그림에서 \(k\) 가 4로 주어진다면, 점선을 따라 격자 A와 B를 잇는 회로의 비용은 19 이지만, 비용이 16인 최소비용 회로가 존재한다. (이 비용에는 격자 A, B의 비용도 포함된다.) |
입력 | |
---|---|
첫째 줄에는 격자 판의 크기를 나타내는 정수 \(n (2 \leq n \leq 50)\) 가 주어진다. 둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다. (시작 격자와 마지막 격자의 위치는 같을 수 없다.) 셋째 줄에는 회로가 배치된 격자를 지나는 데 드는 비용인 정수 \(k\) 가 주어진다. 넷째 줄에는 이미 배치된 회로의 개수가 주어진다. 다섯째 줄부터는 한 줄에 한 회로의 배치 정보가 다음과 같이 주어진다. 첫째 정수는 회로의 시작 격자, \(90^\circ\)로 꺽이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수이고, 그 다음부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다. |
출력 | |
---|---|
첫째 줄에는 회로의 최소 비용을 출력한다. 둘째 줄에는 최소비용 회로의 정보를 다음과 같이 출력한다. (입력 형식과 동일함.) 처음에 회로의 시작 격자, \(90^\circ\)로 꺽이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력하고, 그 다음부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 11 2 3 9 8 4 2 3 3 9 3 4 10 4 4 9 2 7 2 7 7 5 7 | |
출력 | 16 3 2 3 2 8 9 8 |
출처 | |
---|---|
1999년 한국정보올림피아드 전국 본선 중등부 2번 문제 |