[백준: Python] 17141 - 연구소 2

[문제]

https://www.acmicpc.net/problem/17141

바이러스 조합을 찾아서 BFS를 수행하는 문제입니다.

 

바이러스 조합을 찾는 이유는, 어느 위치의 바이러스를 선택했을 때 최소 시간으로 퍼뜨릴 수 있을지 모르기 때문입니다.

---

[초기화]

    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input().split())) for _ in range(self.n)]
        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.answer = float('inf')

---

[풀이]

    def check_virus(self):
        return [(i, j) for i in range(self.n) for j in range(self.n) if self.grid[i][j] == 2]

바이러스의 위치를 담을 메서드입니다.

    def select_virus(self, virus):  # 바이러스 조합 탐색
        result = []

        def select(idx, selected):
            if len(selected) == self.m:
                result.append(selected)
                return
            if idx == len(virus):
                return
            select(idx + 1, selected + [virus[idx]])
            select(idx + 1, selected)

        select(0, [])
        return result

바이러스의 조합을 찾습니다.

 

일반적인 조합 생성 코드로, Python의 경우 라이브러리로 해결 가능합니다.

    def search(self, selected_virus):
        result = 0
        for viruses in selected_virus:
            visited = [[False if self.grid[i][j] != 1 else True for j in range(self.n)] for i in range(self.n)]
            check = [[-1 if self.grid[i][j] != 1 else 1 for j in range(self.n)] for i in range(self.n)]
            dq = deque([])
            max_time = 0
            for virus in viruses:
                y, x = virus
                visited[y][x] = True
                check[y][x] = 0
                dq.append((y, x, 0))

            while dq:
                y, x, time = dq.popleft()
                max_time = max(max_time, time)  # 가장 오래 걸리는 시간
                for dy, dx in self.directions:
                    my, mx = y + dy, x + dx
                    if 0 <= my < self.n and 0 <= mx < self.n and not visited[my][mx]:
                        dq.append((my, mx, time + 1))
                        visited[my][mx] = True
                        check[my][mx] = time + 1

            if sum(i.count(-1) for i in check) == 0:  # 빈 공간이 없을 때만 정답 갱신
                self.answer = min(self.answer, max_time)  # 가장 오래 걸리는 시간 중 최단 시간
            else:
                result += 1

        if result == len(selected_virus):  # 모든 경우를 다 뒤졌음에도 바이러스를 모두 퍼뜨릴 수 없다면
            print(-1)
        else:
            print(self.answer)

모든 조합을 확인하며 BFS를 수행합니다.

 

저는 visited 리스트를 초기화할 때, 처음부터 빈칸(-1)만 탐색할 수 있도록 했습니다.

 

어떤 조합이 최단 시간을 갖는지 확인하는 방법은 현재 조합에서 가장 오래 걸리는 시간 중 최소를 찾으면 됩니다.

 

BFS 탐색이 끝나면, 빈 칸이 있는지 확인합니다.

 

빈칸이 없을 때만 정답을 갱신하고, 아니라면 잘못된 조합이므로 따로 변수에 값을 처리합니다.

 

그렇게 전체 조합에 대한 탐색이 끝났다면, 조합하다 빈칸을 다 채우지 못한 수를 비교합니다.

 

이때, 빈칸을 다 채우지 못한 수와 전체 조합의 수와 같다면, 해당 케이스는 어떠한 방법으로도 빈칸을 다 채울 수 없는 케이스입니다.

---

[전체 코드]

from collections import deque


class Main:
    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input().split())) for _ in range(self.n)]
        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.answer = float('inf')

    def check_virus(self):
        return [(i, j) for i in range(self.n) for j in range(self.n) if self.grid[i][j] == 2]

    def select_virus(self, virus):  # 바이러스 조합 탐색
        result = []

        def select(idx, selected):
            if len(selected) == self.m:
                result.append(selected)
                return
            if idx == len(virus):
                return
            select(idx + 1, selected + [virus[idx]])
            select(idx + 1, selected)

        select(0, [])
        return result

    def search(self, selected_virus):
        result = 0
        for viruses in selected_virus:
            visited = [[False if self.grid[i][j] != 1 else True for j in range(self.n)] for i in range(self.n)]
            check = [[-1 if self.grid[i][j] != 1 else 1 for j in range(self.n)] for i in range(self.n)]
            dq = deque([])
            max_time = 0
            for virus in viruses:
                y, x = virus
                visited[y][x] = True
                check[y][x] = 0
                dq.append((y, x, 0))

            while dq:
                y, x, time = dq.popleft()
                max_time = max(max_time, time)  # 가장 오래 걸리는 시간
                for dy, dx in self.directions:
                    my, mx = y + dy, x + dx
                    if 0 <= my < self.n and 0 <= mx < self.n and not visited[my][mx]:
                        dq.append((my, mx, time + 1))
                        visited[my][mx] = True
                        check[my][mx] = time + 1

            if sum(i.count(-1) for i in check) == 0:  # 빈 공간이 없을 때만 정답 갱신
                self.answer = min(self.answer, max_time)  # 가장 오래 걸리는 시간 중 최단 시간
            else:
                result += 1

        if result == len(selected_virus):  # 모든 경우를 다 뒤졌음에도 바이러스를 모두 퍼뜨릴 수 없다면
            print(-1)
        else:
            print(self.answer)

    def solve(self):
        virus = self.check_virus()
        selected_virus = self.select_virus(virus)
        self.search(selected_virus)


problem = Main()
problem.solve()

---