코딩테스트 연습 - 발전소 회로 복구

문제 설명

대정전이 발생한 발전소는 1~h층으로 이루어진 h층 건물이며, 각 층은 같은 구조의 n×m 크기의 격자로 이루어져 있습니다. 각 칸은 통행 가능한 통로('.'), 통행 불가능한 폐쇄 구역('#'), 엘리베이터('@') 중 하나입니다. 엘리베이터는 격자에서 단 한 칸에만 존재하며 다른 층으로 이동하려면 반드시 엘리베이터를 이용해야 합니다.

통로 중 k곳에는 1~k번의 서로 다른 번호를 가진 회로 패널이 1개씩 설치되어 있습니다. 패널의 위치는 [f, r, c] 형태로 주어지며, f층의 r행 c열에 해당 패널이 위치함을 나타냅니다. 초기에 모든 패널은 비활성화 상태이며, 기술자는 항상 1번 패널이 설치된 위치에서 출발해 모든 회로 패널을 활성화해야 합니다.

기술자는 상하좌우로 인접한 칸으로 1초에 1칸씩 이동할 수 있습니다. 엘리베이터 칸에서만 다른 층으로 이동할 수 있으며, 한 층을 이동할 때마다 1초가 필요합니다. 즉 x층에서 y층으로 이동할 때 |x-y| 만큼 시간이 소요됩니다. 엘리베이터를 기다리는 시간이나 타고 내리는 시간은 고려하지 않습니다.

각 패널은 안전 순서를 따라 활성화해야 합니다. 안전 순서는 여러 개의 [a, b] 쌍으로 이루어져 있으며, b번 패널을 활성화하기 전에 a번 패널이 이미 활성화되어 있어야 함을 나타냅니다.

기술자가 패널이 설치된 칸에 위치할 때 그 패널을 즉시 활성화할 수 있습니다. 단, 안전 순서가 아직 충족되지 않은 패널은 활성화할 수 없습니다. 기술자가 x번 패널을 활성화하기 위해서는 안전 순서에 존재하는 b = x인 모든 [a, b] 쌍에 대해서 모든 a번 패널이 이미 활성화되어 있어야 합니다.

예를 들어, 안전 순서 쌍이 [[3, 1], [4, 1], [5, 1], [2, 3]]이라고 가정해 보겠습니다.
- 1번 패널을 활성화하려면 3, 4, 5번 세 패널이 이미 활성화되어 있어야 합니다.
- 3번 패널을 활성화하려면 2번 패널이 이미 활성화되어 있어야 합니다.
- 2, 4, 5번 패널은 선행 제약 없이 바로 활성화 가능합니다.

당신은 기술자가 모든 패널을 안전하게 활성화하는 데 필요한 최소 시간을 구해야 합니다.

예를 들어 3층인 발전소 내부 구조가 아래 그림과 같다고 가정해 보겠습니다. 엘리베이터가 5행 2열에 위치해 있습니다.

패널의 위치

1번 패널 : 2층 3행 4열
2번 패널 : 2층 5행 6열
3번 패널 : 1층 1행 1열
4번 패널 : 3층 6행 3열

안전 순서 : [[3, 2], [1, 2], [4, 1], [4, 3]]

1번 패널을 활성화하려면 4번 패널이 이미 활성화되어 있어야 합니다.
2번 패널을 활성화하려면 1, 3번 패널이 이미 활성화되어 있어야 합니다.
3번 패널을 활성화하려면 4번 패널이 이미 활성화되어 있어야 합니다.
4번 패널은 선행 제약 없이 바로 활성화 가능합니다.

처음에 기술자가 1번 패널의 위치인 2층 3행 4열에서 출발합니다. 1번 패널은 4번 패널이 활성화되어 있어야 하므로 아직 활성화할 수 없습니다.

빨간색으로 칠해진 격자는 현재 기술자의 위치를 나타냅니다.

엘리베이터로 이동해 2→3층으로 이동합니다. 4번 패널로 이동해 활성화시킵니다. 총 7(= 4 + 1 + 2)초가 걸립니다.

엘리베이터로 이동해 3→1층으로 이동합니다. 3번 패널로 이동해 활성화시킵니다. 총 11(= 2 + 2 + 7)초가 걸립니다.

엘리베이터로 이동해 1→2층으로 이동합니다. 1번 패널로 이동해 활성화시킵니다. 이어서 2번 패널로 이동해 활성화시킵니다. 총 18(= 7 + 1 + 4 + 6)초가 걸립니다.

위와 같은 방법으로 모든 패널을 안전하게 활성화시킬 수 있으며, 총 시간이 36초가 필요합니다. 이보다 빠른 시간 내로 모든 패널을 안전하게 활성화시킬 수는 없습니다.

발전소의 층 수인 정수 h, 발전소 구조 정보를 담은 1차원 문자열 배열 grid, 패널의 위치를 담은 2차원 정수 배열 panels와 안전 순서를 담은 2차원 정수 배열 seqs가 매개변수로 주어집니다. 기술자가 모든 패널을 안전하게 활성화하는 데 필요한 최소 시간을 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ h ≤ 10
2 ≤ grid의 길이 = n ≤ 40
- 2 ≤ grid[i]의 원소 길이 = m ≤ 40
- grid[i][j]는 '.', '#', '@' 중 하나로, i+1행 j+1열 칸의 정보를 나타냅니다. '@'은 격자 내에 반드시 하나만 존재합니다.
2 ≤ panels의 길이 = k ≤ 15
- panels[i]는 [f, r, c] 형태로 i+1번 패널이 f층의 r행 c열 칸에 위치함을 나타냅니다.
- 1 ≤ f ≤ h
- 1 ≤ r ≤ n
- 1 ≤ c ≤ m
- grid[r-1][c-1] = '.'
- panels의 원소는 중복되지 않습니다.
1 ≤ seqs의 길이 ≤ 100
- seqs의 원소는 [a, b] 형태로 b번 패널을 활성화하기 전에 a번 패널이 이미 활성화되어 있어야 함을 나타냅니다.
- 1 ≤ a ≤ k
- 1 ≤ b ≤ k
- a ≠ b
- seqs의 원소는 중복되지 않습니다.
모든 패널을 안전하게 활성화 가능한 경우만 주어집니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

그룹	총점	추가 제한 사항
#1	13%	`k` = 2
#2	18%	`k` ≤ 5
#3	22%	`h` = 1
#4	17%	`seqs`의 길이 = `k-1`, `seqs[i]` = [`i+1`, `i+2`]
#5	30%	추가 제한 사항 없음

입출력 예

h	grid	panels	seqs	result
3	[".#.##..", ".#..##.", ".......", "##.###.", ".@.#...", "...#..."]	[[2, 3, 4], [2, 5, 6], [1, 1, 1], [3, 6, 3]]	[[3, 2], [1, 2], [4, 1], [4, 3]]	36
1	["@......", ".######", ".......", "######.", ".......", ".####..", "....#.."]	[[1, 7, 4], [1, 3, 5], [1, 1, 3]]	[[1, 3], [3, 2]]	31
4	["........#", "........#", "@.......#", ".#.#....#", "........#", "#........", "#.#..####", "..#..####", ".....####"]	[[2, 9, 1], [2, 1, 8], [1, 1, 3], [3, 3, 2], [1, 2, 8]]	[[1, 2], [2, 3], [3, 4], [4, 5]]	47