[Python] 백준 14502 - 연구소 문제 풀이

Overview

BOJ 14502번 연구소 Python 문제 풀이
분류: Graph Traversal (그래프 탐색), dfs, bfs

---

문제 페이지

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

---

풀이 코드 1 - DFS

from sys import stdin
from copy import deepcopy
from typing import List


lab, viruses = [], []
n, m, res = 0, 0, 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def select_walls(start: int, cnt: int) -> None:
    global res

    # 벽 3개 모두 세우면 바이러스 확산 후 안전 지대 탐색
    if cnt == 3:
        lab_copy = deepcopy(lab)
        for y, x in viruses:
            dfs(y, x, lab_copy)
        safezone = sum(i.count(0) for i in lab_copy)
        res = max(safezone, res)
        return

    for i in range(start, n * m):
        y, x = i // m, i % m
        if lab[y][x] == 0:
            lab[y][x] = 1
            select_walls(i, cnt + 1)
            lab[y][x] = 0


def dfs(y: int, x: int, lab_copy: List[List[int]]) -> None:
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < n and 0 <= nx < m and lab_copy[ny][nx] == 0:
            lab_copy[ny][nx] = 2
            dfs(ny, nx, lab_copy)


def cnt_safezone(lab_copy: List[List[int]]) -> int:
    cnt = 0
    for i in range(n):
        for j in range(m):
            if lab_copy[i][j] == 0:
                cnt += 1
    return cnt


def main():
    def input():
        return stdin.readline().rstrip()
    global lab, viruses, n, m

    n, m = map(int, input().split())
    lab = [list(map(int, input().split())) for _ in range(n)]

    # 바이러스 위치 저장
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                viruses.append((i, j))

    # 벽 세우기
    select_walls(0, 0)

    print(res)


if __name__ == "__main__":
    main()

우선 select_walls()에서 백트래킹으로 벽 3개를 빈 공간에 모두 세운다. 그리고 DFS를 이용하여 바이러스를 확산시키키고, 안전지대 개수를 구한다.
바이러스를 확산 시킬 때는lab을 deepcopy하여 복사본에 바이러스를 확산시켜야 한다.

---

풀이 코드 1 - BFS, itertools

from sys import stdin
from typing import List
from itertools import combinations
from collections import deque


lab, viruses, blanks = [], [], []
n, m = 0, 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def bfs(y: int, x: int, lab_copy: List[List[int]]) -> None:
    dq = deque([(y, x)])
    while dq:
        cy, cx = dq.popleft()
        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]
            if 0 <= ny < n and 0 <= nx < m and lab_copy[ny][nx] == 0:
                lab_copy[ny][nx] = 2
                dq.append((ny, nx))


def main():
    def input():
        return stdin.readline().rstrip()
    global lab, viruses, n, m

    n, m = map(int, input().split())
    lab = [list(map(int, input().split())) for _ in range(n)]

    # 바이러스, 빈 공간 위치 저장
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                viruses.append((i, j))
            elif lab[i][j] == 0:
                blanks.append((i, j))

    res = 0
    # 벽 세우기
    combs = combinations(blanks, 3)
    for comb in combs:
        lab_copy = [row[:] for row in lab]
        for y, x in comb:
            lab_copy[y][x] = 1
        # 벽 3개 다 세우면 바이러스 확산
        for y, x in viruses:
            bfs(y, x, lab_copy)
        # 안전 지대 개수 구하기
        safezone = sum(i.count(0) for i in lab_copy)
        res = max(safezone, res)

    print(res)


if __name__ == "__main__":
    main()

이전 풀이와 달리 itertools의 combinations를 이용하여 벽 위치를 선택하였다. 그리고 벽을 세우고 바이러스를 확산시킬 때 BFS 탐색을 이용하였다. 또한 lab을 deepcopy할 때, deepcopy() 메서드를 사용하지 않고 아래 방법을 사용했다.

lab_copy = [row[:] for row in lab]

그리고 안전 지대 개수 세는 방식을 아래와 같이 한 줄로 바꾸었다.

safezone = sum(i.count(0) for i in lab_copy)

채점 결과 수행속도가 이전 코드보다 빨랐다.