[백준 14502] 연구소 (Python)

 

www.acmicpc.net/problem/14502

14502번: 연구소

 

문제 풀이

N, M, board : 입력값

virus : 바이러스 좌표 (x, y)

ans : 결과값(최대 빈 공간)

tmp_board : 원본 board를 훼손하지 않기 위해 복사

q : 바이러스 bfs를 위한 deque

 

bfs(board, virus) : 바이러스를 퍼트리기 위해 bfs로 탐색

 

다소 비효율적이긴 하지만 6중 for문을 통해 3개의 벽을 세우는 것을 구현하였다.

 

1. 3개의 서로 다른 벽 세우기 구현

6중 for문을 통해 벽 세우는 것을 구현한다.

이때 빈 공간이 아닐 경우와 3개 중 하나라도 같은 벽이 있을 경우 continue를 해준다.

 

2. bfs를 통해 바이러스를 퍼트린다. 

바이러스가 동시에 퍼트려져야 하기 때문에 q의 사이즈만큼 반복문을 사용한다.

 

3. 바이러스가 퍼진 후 남아있는 빈 공간을 계산한다.

 

4. 1~3 과정을 모든 경우의 벽을 세울때까지 반복한다.

 

 

코드

import sys
from collections import deque
from copy import deepcopy

def bfs(board, virus):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque(virus)
    # 원본 board 훼손하지 않기 위해 deepcopy로 복사
    tmp_board = deepcopy(board)
    tmp = 0

    # bfs
    while q:
        size = len(q)
        # tmp_board 에 존재하는 바이러스를 동시에 퍼트리게 하기 위해 len(q) 만큼 반복문 실행
        for _ in range(size):
            x, y = q.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if tmp_board[nx][ny] != 0: continue
                    tmp_board[nx][ny] = 2
                    q.append((nx, ny))
    for i in range(N):
        for j in range(M):
            if tmp_board[i][j] == 0: tmp += 1
    return tmp

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    virus = []
    ans = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 2: virus.append((i, j))

    # 1번 벽 세우기
    for x1 in range(N):
        for y1 in range(M):
            if board[x1][y1]: continue # 빈 공간이 아닐 경우 continue
            # 2번 벽 세우기
            for x2 in range(N):
                for y2 in range(M):
                    if board[x2][y2]: continue # 빈 공간이 아닐 경우 continue
                    # 3번 벽 세우기
                    for x3 in range(N):
                        for y3 in range(M):
                            if board[x3][y3]: continue # 빈 공간이 아닐 경우 continue
                            # 벽이 서로 다른 3가지가 될 수 있도록 같으면 continue
                            if x1 == x2 and y1 == y2: continue
                            if x2 == x3 and y2 == y3: continue
                            if x1 == x3 and y1 == y3: continue
                            # 벽 세우기
                            board[x1][y1] = 1
                            board[x2][y2] = 1
                            board[x3][y3] = 1
                            ans = max(ans, bfs(board, virus))
                            # 세웠던 벽 부수기
                            board[x1][y1] = 0
                            board[x2][y2] = 0
                            board[x3][y3] = 0
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!