[Python] 백준 연구소 시리즈

문제 링크

- 연구소 https://www.acmicpc.net/problem/14502

14502번: 연구소

- 연구소 2 https://www.acmicpc.net/problem/17141

17141번: 연구소 2

- 연구소 3 https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

1. 접근 방법

 연구소 시리즈 3문제는 거의 유사하다. 첫 번째 문제는 벽을 설치하는 것이고, 다른 두 문제는 바이러스 중 선택하여 바이러스의 전파를 하면 된다. 정답을 구하는 것은 조금 다르기는 하지만 주어진 점들 중 일부를 선택하는 조합과 각 점에서 전파를 활용하는 BFS를 활용하여 해결할 수 있다.

---

2. 풀이 코드

🖥python 코드 링크

- 연구소 https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/14000/14500/14502.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

- 연구소 2 https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/17000/17100/17141.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

- 연구소 3 https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/17000/17100/17142.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

 

📕코드 해설

1. 연구소
 세 문제 모두 코드가 길어 코드 전체를 첨부하지 않고, 중요한 부분 위주로 그리고 중복되지 않는 코드 위주로 글을 작성하겠다. 추가 코드는 위의 링크를 참고바랍니다.

if __name__ == "__main__":
    N, M = MIIS()
    lab_map = [list(MIIS()) for _ in range(N)]
    blank_places = []
    viruses = []
    for i, line in enumerate(lab_map):
        for j, x in enumerate(line):
            if not x:
                blank_places.append((i, j))
            elif x == 2:
                viruses.append((i, j))
    total_places = len(blank_places)
    viruses_count = len(viruses)
    delta: tuple[tuple[int]] = ((-1, 0), (0, 1), (1, 0), (0, -1))
    ans = 0
    for comb in combinations(blank_places, 3):
        places = search(N, M, lab_map, comb, viruses, delta)
        if ans < (safe_plaecs := total_places - places - 3 + viruses_count):
            ans = safe_plaecs
    print(ans)

 입력받는 부분은 세 문제가 거의 유사하다. 다른 부분은 첫 번째 문제에서는 빈 공간 중 3개를 선택하여 벽을 만들어야 하고, 다른 두 문제는 주어진 바이러스 중 몇 개를 선택해야 한다. 그래서 뒤의 두 문제는 다시 한번 밑에서 다룰 예정이고, 이 문제에서는 모든 빈 공간과 모든 바이러스를 따로 구하였다. 빈 공간은 벽을 설치할 3개의 공간을 구하기 위한 것이고, 바이러스는 탐색 시작점을 구하기 위해서이다.

def search(
    N: int,
    M: int,
    lab_map: Map,
    places: Place,
    viruses: Place,
    delta: tuple[tuple[int]],
) -> int:
    new_lab_map = new_map(lab_map, places)
    queue: deque = deque(viruses)
    visited = [[False] * M for _ in range(N)]
    places_count = 0
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True
        new_lab_map[x][y] = 1
        places_count += 1
        for dx, dy in delta:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if visited[nx][ny]:
                continue
            if new_lab_map[nx][ny] == 1:
                continue
            queue.append((nx, ny))
    return places_count

 탐색을 위한 함수는 위와 같이 구성했다. 새로운 리스트를 만드는 작업은 new_lab_map이라는 함수를 활용해 구했다. 이후 탐색은 모든 비어있는 지점을 탐색하면 되므로 간단한 BFS로 구현했다.

 

2. 연구소 2

blank_places = 0
viruses = []
for i, line in enumerate(lab_map):
    for j, x in enumerate(line):
        if not x:
            blank_places += 1
        elif x == 2:
            viruses.append((i, j))
total_places = blank_places + len(viruses)
delta: tuple[tuple[int]] = ((-1, 0), (0, 1), (1, 0), (0, -1))
ans = 10000
for comb in combinations(viruses, M):
    places, time = search(N, lab_map, comb, delta)

 처음 입력받고 탐색을 위한 부분이 수정이 있어 해당 부분만 가져왔다. 달라진 점은 빈 공간은 개수만 세고, 전체 바이러스 중 M개만 골라서 조합을 선택, 탐색하는 부분이다.

def search(N: int, lab_map: Map, virus: Virus, delta: tuple[tuple[int]]) -> tuple[int]:
    new_lab_map = new_map(lab_map, virus)
    queue: deque = deque([(x, y, 0) for x, y in virus])
    visited = [[False] * N for _ in range(N)]
    places_count = time = 0
    while queue:
        x, y, t = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True
        if time < t:
            time = t
        new_lab_map[x][y] = 3
        places_count += 1
        for dx, dy in delta:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            if new_lab_map[nx][ny] in (1, 3):
                continue
            queue.append((nx, ny, t + 1))
    return places_count, time

 탐색 함수도 변경사항이 있는데, 변경된 지도를 구할 때 선택한 바이러스를 입력으로 넣는다는 점, 선택한 바이러스에서만 탐색을 시작한다는 점이 탐색 시작 부분에서 변경된 부분이고, 탐색 중에서는 선택하지 않은 바이러스 위치는 빈 공간이므로 그냥 탐색하여 빈 공간으로 처리하면 된다.

 

3. 연구소 3

 while queue:
        x, y, t = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True
        if new_lab_map[x][y] != 2:
            if time < t:
                time = t
        new_lab_map[x][y] = 3
        places_count += 1
        for dx, dy in delta:
            # code

 연구소 2와 코드가 거의 같지만, 탐색하는 부분에서 조금 차이가 있어 해당 부분 코드만 가져왔다. 연구소 2에서는 빈 공간 중 바이러스를 놓고 탐색하는, 즉 선택하지 않은 나머지 공간은 빈 공간으로 간주하면 된다. 반면 연구소 3은 ‘비활성 바이러스’가 있다고 한다. 처음에는 잘 이해되지 않았는데, 비활성 바이러스는 시간의 변경 없이 활성화가 되는 것으로 이해했다. 그래서 해당 칸이 2가 아닐 때, 즉 빈 공간일 때는 시간이 더 늘어나면 갱신하고, 아니라면 비활성 바이러스이므로 그냥 활성화(탐색)했다.

 

---

3. 생각 정리

 탐색과 관련한 코드에서는 크게 고생하지 않았는데, 문제마다 조금씩 다른 조건이 약간은 헷갈리기도 했다. 특히 연구소 3의 조건은 모호하다는 느낌도 받았다. 그리고 itertools기능으로 모두 구현했는데, 추후에 조합, 순열 부분도 다시 한번 공부하면 좋을 것 같다.