[BFS/Combination] 백준#14502: 연구소/Python 풀이

📝 문제

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

14502번: 연구소

💡 접근법

1) 문제해결 절차

문제해결 절차는 다음과 같이 크게 3단계입니다.

• 1️⃣ 벽을 세울 수 있는 3개 지점의 모든 조합 찾기
• 2️⃣ 앞서 1️⃣에서 정한 지점에 벽을 세우고 바이러스 전파
• 3️⃣ 가장 넓은 안전지대의 범위 출력

2) 문제해결 방법

BFS 알고리즘을 활용하여 문제를 해결하였습니다. 조합(combination)을 사용한 경우와 하지 않은 경우를 나누어 풀어봤습니다. 각각 나누어 알아봅니다.

💻 첫 번째 풀이: 조합 사용❌

들어가며

첫 번째 풀이는 조합(combination) 모듈을 사용하지 않고 해결하였습니다. PyPy3에서는 패스했으나 Python3에서는 시간 초과가 나왔습니다. 두 번째 풀이에서는 Python3에서도 시간 초과 없이 동작하도록 구현하였습니다. 속도 개선과 정답에 관심 있으신 분은 두 번째 풀이를 참고해 주시길 바랍니다.

1) 전체 코드

import sys; input = sys.stdin.readline
import copy

# 벽 건설 함수
def wall_construct(wall_cnt):
    # 벽 3개 설치 완료 시, 바이러스 전파
    if wall_cnt == 3:
        virus_spread()
        return
    # 벽을 설치할 수 있는 모든 경우의 수 확인
    for n in range(N):
        for m in range(M):
            if board[n][m] == 0:
                board[n][m] = 1 # 벽 설치
                wall_construct(wall_cnt + 1)
                board[n][m] = 0 # 새로운 조합 만들기 위해 초기화

# 바이러스 전파 함수
def virus_spread():
    global answer
    # 기존 맵 정보 깊은 복사(Deep Copy)
    board_wall = copy.deepcopy(board)
    # 바이러스 위치
    virus = [(n, m) for n in range(N) for m in range(M) if board_wall[n][m] == 2]

    # 바이러스마다 전파 끝날 때까지 반복
    while virus:
        x, y = virus.pop()
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M and board_wall[nx][ny] == 0:
                board_wall[nx][ny] = 2
                virus.append((nx, ny)) # 바이러스 전파

    # 안전지대 개수 카운팅
    safezone_cnt = 0
    for row in board_wall:
        safezone_cnt += row.count(0)
    answer = max(answer, safezone_cnt)

if __name__ == "__main__":
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = 0
    wall_construct(0)
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
import copy

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.
• copy 모듈
  • copy 모듈은 맵 정보를 깊은 복사(Deep Copy)하여 벽 3개를 세울 수 있는 모든 경우의 수에서 벽의 건설과 바이러스의 전파를 따로 표현하여 사용하기 위해 import 하였습니다. Deep Copy는 복사된 데이터를 변경해도 원본 데이터가 변경되는 것을 방지합니다.

(2) 벽 건설 함수

# 벽 건설 함수
def wall_construct(wall_cnt):
    # 벽 3개 설치 완료 시, 바이러스 전파
    if wall_cnt == 3:
        virus_spread()
        return
    # 벽을 설치할 수 있는 모든 경우의 수 확인
    for n in range(N):
        for m in range(M):
            if board[n][m] == 0:
                board[n][m] = 1 # 벽 설치
                wall_construct(wall_cnt + 1)
                board[n][m] = 0 # 새로운 조합 만들기 위해 초기화

3개의 벽을 설치할 수 있는 모든 경우의 수를 찾기 위해 재귀함수를 사용하였습니다. 벽 3개를 모두 설치하면 바이러스 전파 함수를 호출합니다.

(3) 바이러스 전파 및 안전지대 계산 함수

# 바이러스 전파 함수
def virus_spread():
    global answer
    # 기존 맵 정보 깊은 복사(Deep Copy)
    board_wall = copy.deepcopy(board)
    # 바이러스 위치
    virus = [(n, m) for n in range(N) for m in range(M) if board_wall[n][m] == 2]

    # 바이러스마다 전파 끝날 때까지 반복
    while virus:
        x, y = virus.pop()
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M and board_wall[nx][ny] == 0:
                board_wall[nx][ny] = 2
                virus.append((nx, ny)) # 바이러스 전파

    # 안전지대 개수 카운팅
    safezone_cnt = 0
    for row in board_wall:
        safezone_cnt += row.count(0)
    answer = max(answer, safezone_cnt)

• 다섯째 줄: 맵 정보 복사
  • 벽 3개가 설치된 맵에 바이러스 전파를 표현하기 위해 Deep Copy를 사용하였습니다. Deep Copy는 복사된 데이터를 변경해도 원본 데이터가 변경되는 것을 방지합니다.
• 7~17째 줄: 바이러스 전파
  • 바이러스 위치를 리스트업하고 상하좌우 방향으로 전파할 수 있을 때까지 좌표를 이동하며 바이러스를 전파합니다.
• 20~23째 줄: 안전지대 개수 카운팅
  
  • 바이러스 전파가 완료되면 안전지대의 개수를 카운팅하여 최대 범위를 출력합니다.

(4) main 함수

if __name__ == "__main__":
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = 0
    wall_construct(0)
    print(answer)

📝 채점 결과

첫 번째 풀이의 채점 결과

채점 결과, PyPy3로 채점했을 때는 통과했으나 Python3로 채점했을 때는 시간 초과가 나왔습니다. PyPy3가 Python3보다는 메모리를 많이 사용해도 속도 측면에서 빠르다 보니 이와 같은 결과가 나온 것으로 보입니다. Python3에서도 시간 초과 없이 문제를 풀기 위해 2번째 풀이를 시작하였습니다.

💻 두 번째 풀이: 조합 사용✅

들어가며

두 번째 풀이에서는 조합(combination) 모듈을 사용하였습니다. PyPy3와 Python3에서 모두 시간 초과 없이 문제를 해결하였습니다. 코드와 설명이 첫 번째 풀이와 겹치는 부분이 있으니 2가지 풀이를 모두 보시는 분들께서는 이 점 참고해 주시길 바랍니다😊

1) 전체 코드

import sys; input = sys.stdin.readline
import copy
from itertools import combinations

def solve():
    global answer
    # 새롭게 세울 벽 3개의 모든 조합 얻기
    for wall_combi in combinations(empty, wall_num):
        # 기존 맵 정보 깊은 복사(Deep Copy)
        board_new = copy.deepcopy(board)
        for x_w, y_w in wall_combi:
            board_new[x_w][y_w] = 1
        # 바이러스 위치
        virus = [(n, m) for n in range(N) for m in range(M) if board_new[n][m] == 2]
        # 바이러스마다 전파 끝날 때까지 반복
        while virus:
            x_v, y_v = virus.pop()
            for dx, dy in direction:
                nx = x_v + dx
                ny = y_v + dy
                if 0 <= nx < N and 0 <= ny < M and board_new[nx][ny] == 0:
                    board_new[nx][ny] = 2
                    virus.append((nx, ny)) # 바이러스 전파
        # 안전지대 개수 카운팅
        safezone_cnt = 0
        for row in board_new:
            safezone_cnt += row.count(0)
        answer = max(answer, safezone_cnt)

if __name__ == "__main__":
    N, M = map(int, input().split())
    wall_num = 3
    board = [list(map(int, input().split())) for _ in range(N)]
    # 벽을 세울 수 있는 빈 공간 정보를 리스트에 저장
    empty = [(n, m) for n in range(N) for m in range(M) if board[n][m] == 0]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = 0
    solve()
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
import copy
from itertools import combinations

• sys 모듈
  • 파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.
• copy 모듈
  • copy 모듈은 맵 정보를 깊은 복사(Deep Copy)하여 벽 3개를 세울 수 있는 모든 경우의 수에서 벽의 건설과 바이러스의 전파를 따로 표현하여 사용하기 위해 import 하였습니다. Deep Copy는 복사된 데이터를 변경해도 원본 데이터가 변경되는 것을 방지합니다.

• combinations 모듈
  • 순서를 고려하지 않고 전체 원소 중 \(N\)개 뽑는 경우의 수를 구해주는 조합(Combination)을 지원합니다.

(2) main 함수

if __name__ == "__main__":
    N, M = map(int, input().split())
    wall_num = 3
    board = [list(map(int, input().split())) for _ in range(N)]
    # 벽을 세울 수 있는 빈 공간 정보를 리스트에 저장
    empty = [(n, m) for n in range(N) for m in range(M) if board[n][m] == 0]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = 0
    solve()
    print(answer)

메인 함수에 벽을 설치할 수 있는 곳의 정보를 empty 변수에 이중 리스트로 저장하였습니다.

(3) 풀이

def solve():
    global answer
    # 새롭게 세울 벽 3개의 모든 조합 얻기
    for wall_combi in combinations(empty, wall_num):
        # 기존 맵 정보 깊은 복사(Deep Copy)
        board_new = copy.deepcopy(board)
        for x_w, y_w in wall_combi:
            board_new[x_w][y_w] = 1
        # 바이러스 위치
        virus = [(n, m) for n in range(N) for m in range(M) if board_new[n][m] == 2]
        # 바이러스마다 전파 끝날 때까지 반복
        while virus:
            x_v, y_v = virus.pop()
            for dx, dy in direction:
                nx = x_v + dx
                ny = y_v + dy
                if 0 <= nx < N and 0 <= ny < M and board_new[nx][ny] == 0:
                    board_new[nx][ny] = 2
                    virus.append((nx, ny)) # 바이러스 전파
        # 안전지대 개수 카운팅
        safezone_cnt = 0
        for row in board_new:
            safezone_cnt += row.count(0)
        answer = max(answer, safezone_cnt)

• 넷째 줄: 벽 설치할 수 있는 모든 경우의 수(조합)
  • Combination을 활용하여 벽을 설치할 수 있는 정보를 담은 empty(리스트)에서 3개의 조합을 만듭니다.
• 여섯째 줄: 맵 정보 복사
  • 벽 3개가 설치된 맵에 바이러스 전파를 표현하기 위해 Deep Copy를 사용하였습니다. Deep Copy는 복사된 데이터를 변경해도 원본 데이터가 변경되는 것을 방지합니다.
• 12~19째 줄: 바이러스 전파
  • 바이러스 위치를 리스트업하고 상하좌우 방향으로 전파할 수 있을 때까지 좌표를 이동하며 바이러스를 전파합니다.
• 21~24째 줄: 안전지대 개수 카운팅
  • 바이러스 전파가 완료되면 안전지대의 개수를 카운팅하여 최대 범위를 출력합니다.

📝 채점 결과

2번째 풀이의 채점 결과

두 번째 풀이 채점 결과, PyPy3에서는 속도가 5배 이상 개선되었으며, Python3에서도 시간 초과 없이 패스된 것을 확인하실 수 있습니다.

💾 Github

• 첫 번째 풀이: 조합 사용❌
  • https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14502.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

• 두 번째 풀이: 조합 사용✅
  • https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14502_combi.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.